Problem #30: Substring with Concatenation of All Words

Intuition & Strategy Breakdown

Use a sliding window with hash map counts of words. Move the window by word length steps, tracking word frequencies to ensure all words are matched exactly once without overlap.

Python Solution

class Solution:
    def findSubstring(self, s: str, words: list[str]) -> list[int]:
        if not s or not words: return []
        word_len, word_count = len(words[0]), len(words)
        total_len = word_len * word_count
        word_map = collections.Counter(words)
        res = []
        for i in range(len(s) - total_len + 1):
            seen = collections.defaultdict(int)
            for j in range(word_count):
                word_idx = i + j * word_len
                word = s[word_idx:word_idx + word_len]
                if word not in word_map: break
                seen[word] += 1
                if seen[word] > word_map[word]: break
            else:
                res.append(i)
        return res

Java Solution

class Solution {
    public List findSubstring(String s, String[] words) {
        List res = new ArrayList<>();
        if (s == null || words == null || words.length == 0) return res;
        int wordLen = words[0].length(), wordCount = words.length;
        Map wordMap = new HashMap<>();
        for (String w : words) wordMap.put(w, wordMap.getOrDefault(w, 0) + 1);
        
        for (int i = 0; i <= s.length() - wordLen * wordCount; i++) {
            Map seen = new HashMap<>();
            int j = 0;
            while (j < wordCount) {
                String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
                if (!wordMap.containsKey(word)) break;
                seen.put(word, seen.getOrDefault(word, 0) + 1);
                if (seen.get(word) > wordMap.get(word)) break;
                j++;
            }
            if (j == wordCount) res.add(i);
        }
        return res;
    }
}