A complete visual walkthrough of the sliding window approach with word-sized steps.
The naive approach: for each starting index in s, extract a substring of length wordCount * wordLen, split it into word-sized chunks, and check if those chunks form a permutation of the target words.
We need to find starting indices where a 6-character substring is a concatenation of "foo" and "bar" (in any order).
The brute force checks each of the ~n positions, splits into ~wordCount chunks, and compares each chunk. This gives O(n * wordCount * wordLen) — very slow for large inputs.
The key observation: All words have equal length. This means we can slide a window that moves in word-sized steps, reusing work from previous positions instead of rechecking everything.
Since all words have the same length w, we can treat the string as a sequence of word-sized slots. We run w different passes (starting at offsets 0, 1, ..., w-1) and in each pass, slide a window by one word at a time.
words array.i. Extract words at positions i, i+w, i+2w, ...count == wordCount, record the left index.Why multiple offsets? Words could start at any character position mod wordLen. For wordLen=3, the word boundaries starting at index 0 are different from those starting at index 1 or 2. We run a pass for each possible alignment to cover all cases.
Let's trace the algorithm with s = "barfoothefoobarman" and words = ["foo", "bar"]. With wordLen=3, we run 3 passes (offsets 0, 1, 2). The interesting one is offset 0.
s.length() < wordCount * wordLen, no valid substring can exist. Return an empty list.class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> result = new ArrayList<>(); int wordLen = words[0].length(); int wordCount = words.length; int totalLen = wordLen * wordCount; // Build target frequency map Map<String, Integer> target = new HashMap<>(); for (String w : words) target.merge(w, 1, Integer::sum); // Try each starting offset (0 to wordLen-1) for (int i = 0; i < wordLen; i++) { Map<String, Integer> window = new HashMap<>(); int left = i, count = 0; // Slide through word-sized chunks for (int j = i; j + wordLen <= s.length(); j += wordLen) { String word = s.substring(j, j + wordLen); if (target.containsKey(word)) { window.merge(word, 1, Integer::sum); count++; // Shrink if this word exceeds target count while (window.get(word) > target.get(word)) { String leftWord = s.substring(left, left + wordLen); window.merge(leftWord, -1, Integer::sum); count--; left += wordLen; } // All words matched! if (count == wordCount) result.add(left); } else { // Unknown word — reset everything window.clear(); count = 0; left = j + wordLen; } } } return result; } }
Enter a string and words to find all concatenation substring indices.
We run w passes (where w = word length). Each pass scans the entire string once, extracting substrings of length w at each step. Total: O(n * w) where n is the string length. The space is dominated by the two HashMaps holding at most m entries (m = number of words), each with keys of length w.
Compared to brute force: The brute force is O(n * m * w) because it re-checks all words at every position. The sliding window eliminates the factor of m by reusing previous computations — when we slide right by one word, we only add one word and potentially remove one from the left.