#30 Substring with Concatenation of All Words
the problem
In plain words
Every string in words has the same length w. A "concatenation" is all the words joined end to end in any order, each used exactly as many times as it appears in the list. Return every index of s where such a concatenation begins, in any order.
in s = "barfoothefoobarman", words = ["foo","bar"]
out [0,9]
"barfoo" starts at 0 and "foobar" starts at 9.
in s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
out []
"word" is needed twice, and no 16-letter stretch has two of them plus "good" and "best".
in s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
out [6,9,12]
- 1 ≤ s.length ≤ 10⁴
- 1 ≤ words.length ≤ 5000
- 1 ≤ words[i].length ≤ 30, all the same
- Lowercase English letters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSliding window (variable size)Frequency counting
Treat each word as one "letter". Starting at an offset r (0 ≤ r < w), s splits into a grid of w-letter words, and on that grid this is an ordinary sliding window with a HashMap of word counts.
solutions
From brute force to optimal
From each start, cut k words of length w and count them; stop at the first unknown or over-used word.
- need = counts of words.
- For each start i with room for k words: cut words one by one into a fresh
seenmap. - A word not in need, or seen more often than needed → stop. All k matched → record i.
Up to n starts, each cutting up to k words, and every cut + hash costs O(w).
The need map and one seen map hold up to k words of w letters.
class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> starts = new ArrayList<>(); int w = words[0].length(), k = words.length; Map<String, Integer> need = new HashMap<>(); for (String word : words) need.merge(word, 1, Integer::sum); for (int i = 0; i + w * k <= s.length(); i++) { Map<String, Integer> seen = new HashMap<>(); int j = 0; while (j < k) { // cut the next word and count it String word = s.substring(i + j * w, i + (j + 1) * w); if (seen.merge(word, 1, Integer::sum) > need.getOrDefault(word, 0)) break; // unknown or over-used j++; } if (j == k) starts.add(i); // all k words matched exactly } return starts; }}For each offset 0..w−1, slide over s word by word, keeping the window's word counts; never re-count a word you already counted on that offset.
- need = counts of words; k = words.length.
- For each offset: left = offset, count = 0, empty
have. - Cut the next word at right. Unknown word → clear the window and restart at right + w.
- Known → add it; while that word is over-used, remove the word at left and move left by w.
- If count == k, record left.
w offsets × about n / w words each, left never passes right, and each cut + hash is O(w): w · (n / w) · w = n · w. Building need costs k · w.
Two maps with at most k words of w letters.
class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> starts = new ArrayList<>(); int w = words[0].length(), k = words.length; Map<String, Integer> need = new HashMap<>(); for (String word : words) need.merge(word, 1, Integer::sum); for (int offset = 0; offset < w; offset++) { // w separate "word grids" Map<String, Integer> have = new HashMap<>(); int left = offset, count = 0; // count = words inside the window for (int right = offset; right + w <= s.length(); right += w) { String word = s.substring(right, right + w); if (!need.containsKey(word)) { // a stranger: no answer can cover it have.clear(); count = 0; left = right + w; // restart just after it continue; } have.merge(word, 1, Integer::sum); count++; while (have.get(word) > need.get(word)) { // one copy too many: shrink from the left have.merge(s.substring(left, left + w), -1, Integer::sum); count--; left += w; } if (count == k) starts.add(left); // exactly the k words, in some order } } return starts; }}in the room
How to say it in the interview
talk track
- Clarify: words can repeat (counts matter), all words have the same length, any order of output is fine.
- Brute force: for each start, cut k words and compare counts — O(n·k·w).
- Key step out loud: "a word is a letter on a grid". There are only w grids, one per offset, and each is a normal variable window with a HashMap.
- Name the three moves: unknown word → reset; over-used word → shrink from the left; k words inside → record.
traps
- Only trying offset 0 — an answer can start at any of the w offsets.
- Comparing word sets instead of counts — ["word", "word"] needs two copies.
- Starting a fresh count at every single index — that is the brute force's n·k·w cost.
what they ask next
Follow-ups
Why not just take a fixed window of k·w letters at every start?
That is the brute force: each start re-cuts and re-counts k words. On a word grid, each word enters and leaves the window once per offset.
How is this like Minimum Window Substring (LC 76)?
Same need/have bookkeeping with a shrink loop — but over words instead of characters, and the window must hold exactly k words.
before you submit
Edge cases to test
- Repeated words: ["a", "a"] in "aaaa" → [0, 1, 2] — counts, not sets.
- The words together are longer than s → an empty list.
- An answer off offset 0: "xfoobar" with ["foo", "bar"] → [1].
- A word that isn't in the list resets the window on that offset.
practise next
Similar problems
- #438Find All Anagrams in a StringMediumin Sliding Window
- #76Minimum Window SubstringHardin Sliding Window
- #49Group AnagramsMediumin Arrays & Strings