Sliding Window — Substring with Concatenation of All Words
↗ LeetCode: Substring with Concatenation of All Words · Hard · pattern chapter →
Find starting indices of substrings that are concatenations of every word in words (each used exactly once, any order). All words same length L.
Example 1 — s="barfoothefoobarman", words=["foo","bar"] → [0, 9]Example 2 — s="wordgoodgoodgoodbestword", words=["word","good","best","word"] → []
Constraints — 1 ≤ |s| ≤ 10⁴; each word ≤ 30 chars. Brute checks every window against every permutation — O(n·k!·L) blows up past k=8. Sliding window with word-frequency map is O(n·L) = ~10⁶ ops.
Interview timer00:00
Approach 1 — Try every start
O(n · k · L). Baseline.
Approach 2 — Sliding window on word-aligned offsets (canonical)
Insight. Iterate offset ∈ [0, L). Walk s in chunks of L. Maintain have count; on unknown word, reset window; on over-count, shrink from left.
List<Integer> findSubstring(String s, String[] words) {
List<Integer> out = new ArrayList<>();
int L = words[0].length(), k = words.length;
int total = L * k;
if (s.length() < total) return out;
Map<String, Integer> need = new HashMap<>();
for (String w : words) need.merge(w, 1, Integer::sum);
for (int off = 0; off < L; off++) {
int l = off, have = 0;
Map<String, Integer> win = new HashMap<>();
for (int r = off; r + L <= s.length(); r += L) {
String w = s.substring(r, r + L);
if (!need.containsKey(w)) { win.clear(); have = 0; l = r + L; continue; }
win.merge(w, 1, Integer::sum);
have++;
while (win.get(w) > need.get(w)) {
String lw = s.substring(l, l + L);
win.merge(lw, -1, Integer::sum);
have--;
l += L;
}
if (have == k) out.add(l);
}
}
return out;
}Complexity — Time O(n · L); Space O(k · L).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Every start | O(n · k · L) | O(k) | baseline |
| Aligned sliding | O(n · L) | O(k · L) | canonical |
When to use which
- Fixed-length words concat → offset-aligned sliding.
- Variable-length words → totally different — DP on word breaks.
- Return only count → same skeleton, count instead of appending.