Substring with Concatenation of All Words

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        const int m = words.size(), w = words[0].size();
        const int totalLen = m * w;
        vector<int> ans;
        if ((int)s.size() < totalLen) return ans;
        unordered_map<string,int> need;
        for (auto& wd : words) ++need[wd];
        for (int offset = 0; offset < w; ++offset) {
            int left = offset, count = 0;
            unordered_map<string,int> have;
            for (int right = offset; right + w <= (int)s.size(); right += w) {
                string token = s.substr(right, w);
                if (!need.count(token)) {
                    have.clear(); count = 0; left = right + w;
                    continue;
                }
                ++have[token]; ++count;
                while (have[token] > need[token]) {
                    --have[s.substr(left, w)];
                    --count;
                    left += w;
                }
                if (count == m) {
                    ans.push_back(left);
                    --have[s.substr(left, w)];
                    --count;
                    left += w;
                }
            }
        }
        return ans;
    }
};

func findSubstring(s string, words []string) []int {
    m, w := len(words), len(words[0])
    totalLen := m * w
    ans := []int{}
    if len(s) < totalLen {
        return ans
    }
    need := map[string]int{}
    for _, wd := range words {
        need[wd]++
    }
    for offset := 0; offset < w; offset++ {
        left, count := offset, 0
        have := map[string]int{}
        for right := offset; right+w <= len(s); right += w {
            token := s[right : right+w]
            if _, ok := need[token]; !ok {
                have = map[string]int{}
                count = 0
                left = right + w
                continue
            }
            have[token]++
            count++
            for have[token] > need[token] {
                have[s[left:left+w]]--
                count--
                left += w
            }
            if count == m {
                ans = append(ans, left)
                have[s[left:left+w]]--
                count--
                left += w
            }
        }
    }
    return ans
}

from collections import Counter, defaultdict
from typing import List

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        m, w = len(words), len(words[0])
        total_len = m * w
        ans: List[int] = []
        if len(s) < total_len:
            return ans
        need = Counter(words)
        for offset in range(w):
            left = offset
            count = 0
            have: dict = defaultdict(int)
            right = offset
            while right + w <= len(s):
                token = s[right:right + w]
                if token not in need:
                    have.clear()
                    count = 0
                    left = right + w
                else:
                    have[token] += 1
                    count += 1
                    while have[token] > need[token]:
                        have[s[left:left + w]] -= 1
                        count -= 1
                        left += w
                    if count == m:
                        ans.append(left)
                        have[s[left:left + w]] -= 1
                        count -= 1
                        left += w
                right += w
        return ans

function findSubstring(s, words) {
    const m = words.length, w = words[0].length;
    const totalLen = m * w;
    const ans = [];
    if (s.length < totalLen) return ans;
    const need = new Map();
    for (const wd of words) need.set(wd, (need.get(wd) || 0) + 1);
    for (let offset = 0; offset < w; offset++) {
        let left = offset, count = 0;
        const have = new Map();
        for (let right = offset; right + w <= s.length; right += w) {
            const token = s.substring(right, right + w);
            if (!need.has(token)) {
                have.clear();
                count = 0;
                left = right + w;
                continue;
            }
            have.set(token, (have.get(token) || 0) + 1);
            count++;
            while (have.get(token) > need.get(token)) {
                const leftTok = s.substring(left, left + w);
                have.set(leftTok, have.get(leftTok) - 1);
                count--;
                left += w;
            }
            if (count === m) {
                ans.push(left);
                const leftTok = s.substring(left, left + w);
                have.set(leftTok, have.get(leftTok) - 1);
                count--;
                left += w;
            }
        }
    }
    return ans;
}

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int m = words.length, w = words[0].length();
        int totalLen = m * w;
        List<Integer> ans = new ArrayList<>();
        if (s.length() < totalLen) return ans;
        Map<String, Integer> need = new HashMap<>();
        for (String wd : words) need.merge(wd, 1, Integer::sum);
        for (int offset = 0; offset < w; offset++) {
            int left = offset, count = 0;
            Map<String, Integer> have = new HashMap<>();
            for (int right = offset; right + w <= s.length(); right += w) {
                String token = s.substring(right, right + w);
                if (!need.containsKey(token)) {
                    have.clear();
                    count = 0;
                    left = right + w;
                    continue;
                }
                have.merge(token, 1, Integer::sum);
                count++;
                while (have.get(token) > need.get(token)) {
                    String leftTok = s.substring(left, left + w);
                    have.merge(leftTok, -1, Integer::sum);
                    count--;
                    left += w;
                }
                if (count == m) {
                    ans.add(left);
                    String leftTok = s.substring(left, left + w);
                    have.merge(leftTok, -1, Integer::sum);
                    count--;
                    left += w;
                }
            }
        }
        return ans;
    }
}

function findSubstring(s: string, words: string[]): number[] {
    const m: number = words.length, w: number = words[0].length;
    const totalLen: number = m * w;
    const ans: number[] = [];
    if (s.length < totalLen) return ans;
    const need: Map<string, number> = new Map();
    for (const wd of words) need.set(wd, (need.get(wd) || 0) + 1);
    for (let offset = 0; offset < w; offset++) {
        let left: number = offset, count: number = 0;
        const have: Map<string, number> = new Map();
        for (let right = offset; right + w <= s.length; right += w) {
            const token: string = s.substring(right, right + w);
            if (!need.has(token)) {
                have.clear();
                count = 0;
                left = right + w;
                continue;
            }
            have.set(token, (have.get(token) || 0) + 1);
            count++;
            while ((have.get(token) as number) > (need.get(token) as number)) {
                const leftTok: string = s.substring(left, left + w);
                have.set(leftTok, (have.get(leftTok) as number) - 1);
                count--;
                left += w;
            }
            if (count === m) {
                ans.push(left);
                const leftTok: string = s.substring(left, left + w);
                have.set(leftTok, (have.get(leftTok) as number) - 1);
                count--;
                left += w;
            }
        }
    }
    return ans;
}