A complete visual walkthrough of the sliding window approach with word-sized steps.
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.
words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation:
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation:
There is no concatenated substring.
Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation:
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"].
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"].
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].
Constraints:
1 <= s.length <= 1041 <= words.length <= 50001 <= words[i].length <= 30s and words[i] consist of lowercase English letters.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; } }
func findSubstring(s string, words []string) []int { result := []int{} wordLen := len(words[0]) wordCount := len(words) // Build target frequency map target := make(map[string]int) for _, w := range words { target[w]++ } // Try each starting offset (0 to wordLen-1) for i := 0; i < wordLen; i++ { window := make(map[string]int) left, count := i, 0 // Slide through word-sized chunks for j := i; j+wordLen <= len(s); j += wordLen { word := s[j : j+wordLen] if _, ok := target[word]; ok { window[word]++ count++ // Shrink if this word exceeds target count for window[word] > target[word] { leftWord := s[left : left+wordLen] window[leftWord]-- count-- left += wordLen } // All words matched! if count == wordCount { result = append(result, left) } } else { // Unknown word — reset everything window = make(map[string]int) count = 0 left = j + wordLen } } } return result }
from collections import Counter def find_substring(s: str, words: list[str]) -> list[int]: result: list[int] = [] word_len = len(words[0]) word_count = len(words) # Build target frequency map target = Counter(words) # Try each starting offset (0 to word_len-1) for i in range(word_len): window: dict[str, int] = {} left, count = i, 0 # Slide through word-sized chunks j = i while j + word_len <= len(s): word = s[j:j + word_len] if word in target: window[word] = window.get(word, 0) + 1 count += 1 # Shrink if this word exceeds target count while window[word] > target[word]: left_word = s[left:left + word_len] window[left_word] -= 1 count -= 1 left += word_len # All words matched! if count == word_count: result.append(left) else: # Unknown word — reset everything window.clear() count = 0 left = j + word_len j += word_len return result
use std::collections::HashMap; impl Solution { pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> { let mut result = Vec::new(); let word_len = words[0].len(); let word_count = words.len(); let s_bytes = s.as_bytes(); // Build target frequency map let mut target: HashMap<&str, usize> = HashMap::new(); for w in &words { *target.entry(w.as_str()).or_insert(0) += 1; } // Try each starting offset (0 to word_len-1) for i in 0..word_len { let mut window: HashMap<&str, usize> = HashMap::new(); let (mut left, mut count) = (i, 0usize); // Slide through word-sized chunks let mut j = i; while j + word_len <= s.len() { let word = std::str::from_utf8(&s_bytes[j..j + word_len]).unwrap(); if target.contains_key(word) { *window.entry(word).or_insert(0) += 1; count += 1; // Shrink if this word exceeds target count while window[word] > target[word] { let lw = std::str::from_utf8(&s_bytes[left..left + word_len]).unwrap(); *window.get_mut(lw).unwrap() -= 1; count -= 1; left += word_len; } // All words matched! if count == word_count { result.push(left as i32); } } else { // Unknown word — reset everything window.clear(); count = 0; left = j + word_len; } j += word_len; } } result } }
function findSubstring(s: string, words: string[]): number[] { const result: number[] = []; const wordLen = words[0].length; const wordCount = words.length; // Build target frequency map const target = new Map<string, number>(); for (const w of words) target.set(w, (target.get(w) ?? 0) + 1); // Try each starting offset (0 to wordLen-1) for (let i = 0; i < wordLen; i++) { const window = new Map<string, number>(); let left = i, count = 0; // Slide through word-sized chunks for (let j = i; j + wordLen <= s.length; j += wordLen) { const word = s.slice(j, j + wordLen); if (target.has(word)) { window.set(word, (window.get(word) ?? 0) + 1); count++; // Shrink if this word exceeds target count while (window.get(word)! > target.get(word)!) { const leftWord = s.slice(left, left + wordLen); window.set(leftWord, window.get(leftWord)! - 1); count--; left += wordLen; } // All words matched! if (count === wordCount) result.push(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.
Where n = string length, m = number of words, and k = word length. We run k offset passes. Within each pass, the sliding window scans n/k word-sized chunks, and extracting each substring costs O(k). The window map holds at most m entries, and each hash comparison costs O(k), giving O(n × m × k) worst case. Space is O(m) for the two hash maps (target + window).
For each of the n starting positions, extract m word-sized chunks (each costing O(k) to slice and hash), then compare their frequency map against the target. The nested structure -- n positions times m words times k characters per hash -- gives O(n*m*k). A hash map of up to m entries is rebuilt at every position.
We run k offset passes (0 to k-1). Within each pass the sliding window advances one word at a time across n/k positions, adding one word on the right and removing at most one on the left -- eliminating the factor of m per step. Each substring extraction costs O(k), giving O(n*k) total. The window hash map holds at most m entries.
The sliding window slides k positions at a time, checking word-sized chunks. Instead of re-validating all m words at every starting position, the window adds one word on the right and removes at most one on the left -- eliminating the factor of m per step in practice.
Review these before coding to avoid predictable interview regressions.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.