Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
All words have the SAME length L, so any valid concatenation is a block of L-sized chunks. Build a need-count map of the words. The brute force checks every start index by chopping the next k·L characters into words and matching counts (O(n·k) or O(n·k·L)). The optimal runs L sliding windows — one per alignment offset 0..L-1 — stepping by L word-by-word, maintaining a window count map and shrinking from the left on overflow, for O(n·L) time.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you exploit the fixed word length to reduce a daunting concatenation problem to a count-map comparison, and whether you can upgrade the brute force into an amortized sliding window across L alignment offsets.
Where candidates slip
Re-chopping and re-counting the full block at every single start index (correct but slow), or sliding by 1 character instead of by word length, or forgetting to shrink the window on overflow so counts drift.
How to stand out
Lead with 'all words are the same length, so a valid match is k aligned chunks'. Give the brute force, then derive the L-offset sliding window and explain why each character is processed O(1) times per offset.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAll words length L, k words totalCheck every start index?Brute forceAmortizedExplore the full treeCollapse the tree
s = "barfoothefoobarman", words = ["foo","bar"]How to read it:Stepping by L=3 through "barfoothe..."; the window count map matches need at left=0.
- Frame 1
right=0, "bar"bar in need → window[bar]=1, count=1
bar→ 1Match found. - Frame 2
right=3, "foo"foo in need → window[foo]=1, count=2 → full, record left=0
bar→ 1foo→ 1Match found. - Frame 3
right=6, "the"the NOT in need → reset window, left=9
map = {} (empty)Looked upthe— not in map.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Check Every Start Index
1Hint 1Explore hintHide hint
All words share length L and there are k of them, so any match occupies exactly k·L characters. How many start indices are even worth checking?
2Hint 2Explore hintHide hint
For each start i where i + k·L ≤ n, chop the block into k chunks of length L and tally them in a 'seen' map; compare against the 'need' map built from words.
3Hint 3Explore hintHide hint
Bail early: the moment a chunk isn't a needed word, or its seen-count exceeds its need-count, this start fails — move to i+1.
A · Core idea
Start by exploiting the one fact that tames the problem: every word has the same length L, and there are k = words.length of them, so any valid concatenation is exactly k·L characters long. That means only start indices i with i + k·L ≤ n can possibly match — and at each such i, the candidate substring is just k back-to-back chunks of length L.
Reducing the match to count equality. Build a need map once: word → how many times it must appear. For a given start i, walk the k chunks s[i], s[i+L], s[i+2L], …, tallying each into a fresh seen map. The substring matches iff seen equals need as multisets — order is irrelevant, only counts matter. Because we use counts rather than a set, duplicate words in words are handled correctly (a word needed twice must be seen twice).
Why early termination keeps it practical. We don't have to build the whole seen map before deciding. As we extract each chunk we check two things: (1) is the chunk even a needed word? If not, this start is dead — break. (2) Has this word now been seen more times than need allows? If so, also dead — break. Either failure lets us abandon start i immediately and try i+1. On random text most starts die after one or two chunks, so the practical cost is far below the worst case.
Why it's correct but not what they want. Each of the O(n) start positions can, in the worst case, scan all k chunks, and extracting/hashing a length-L chunk costs up to O(L). That's O(n·k·L). The redundancy is obvious once you see it: adjacent start indices that are multiples of L apart re-examine the same chunks over and over. The optimal approach eliminates exactly that re-work by sliding a window instead of rebuilding seen from scratch — which is the natural next thing to propose.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "barfoothefoobarman", words = ["foo","bar"]i=0
chunks bar, foo — both needed, counts match
match → add 0[0, 9]C · Code with teaching comments
Reference implementation previewpublic List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); int k = words.length; if (k == 0) return res; int L = words[0].length();Explore the full codeHide the full code
D · Why it works and complexityO(n · k · L) timeO(k · L) spaceOpen the invariant and proofExplore the proofHide the proof
The equal-length property collapses a scary 'find all concatenations' problem into 'compare two multisets of fixed-size chunks'. Once you frame matching as count-map equality with early exit, the brute force is short and obviously correct — the perfect springboard for the sliding-window optimization.
ComplexityO(n · k · L) time, O(k · L) space — There are O(n) start indices; each does up to k substring-and-hash operations of length L → O(n·k·L), or O(n·k) if you treat substring hashing as O(1) amortized. The maps hold O(k) words of length L → O(k·L) space.
E · Edge cases and pitfalls5s shorter than k·L — Loop never runs (guarded) → empty list.Explore edge casesHide edge cases
Edge cases handled
s shorter than k·LLoop never runs (guarded) → empty list.words with a duplicate, e.g. [foo, foo]need[foo]=2; a window with only one foo fails the count, two foos matches.
Pitfalls
- Using a set instead of a count map — breaks when words has duplicates.
- Comparing sequence equality instead of multiset equality — order shouldn't matter.
- Forgetting the early break, doing full O(k) work even on hopeless starts.
Approach 2 of 2 · Optimal
Sliding Window over L Offsets (Optimal)
1Hint 1Explore hintHide hint
The brute force re-examines the same chunks for many start indices. Adjacent valid starts differ by L, so group starts by their alignment: offset 0, 1, …, L-1.
2Hint 2Explore hintHide hint
For a fixed offset, the string is a sequence of words at positions offset, offset+L, offset+2L, …. Slide a window over THAT sequence, keeping a running count map and a count of how many words are in the window.
3Hint 3Explore hintHide hint
Expand right by one word each step. If a word over-fills (count > need) shrink from the left until it's valid. When the window holds exactly k words, record left, then drop one word to keep sliding.
A · Core idea
The brute force's waste is that start indices that are multiples of L apart re-chop the very same words. The sliding window removes that waste by processing each alignment offset as one continuous left-to-right sweep, reusing work between consecutive starts.
Why L separate windows. A valid match always begins at some index i, and within that match the word boundaries fall at i, i+L, i+2L, …. Two starts share their chunk boundaries exactly when they are congruent modulo L. So we partition all possible starts into L classes by start mod L. For each offset 0 ≤ offset < L, the substring s viewed from that offset is a clean sequence of consecutive words, and a single sliding window over that sequence discovers every match in that class. Doing all L offsets covers every possible start with no overlap and no omission.
The window mechanics. Within one offset we keep left (the window's start), a window count map of the words currently inside, and count (how many words are in the window). We advance right by L each step, reading the next word w:
- If
wis not a needed word, the whole window is invalidated — clear the map, resetcount = 0, and jumpleftpastw. Nothing ending at or beforewcan be part of a match, so we skip cleanly. - If
wis needed, add it to the window and incrementcount. Now it may be over-represented: whilewindow[w] > need[w], drop the leftmost word (window[leftWord]--,left += L,count--). This shrink restores the invariant that no word exceeds its required count, discarding the earliest copies that caused the overflow. - When
count == k, the window holds exactly the required multiset — recordleftas a match. Then slide forward by dropping the leftmost word so the search continues for the next window.
Why each character is processed O(1) times per offset. Across a single offset sweep, right moves forward monotonically and left only ever moves forward too. Every word position is added to the window once (when right passes it) and removed at most once (when left passes it). So the total add/remove work per offset is linear in the number of word positions, O(n/L). Multiplying by the O(L) cost to slice and hash each length-L word, and summing over L offsets, gives O(n·L) — a clear win over the brute force's O(n·k·L) whenever k is large.
Why shrinking beats restarting. The naive fix on overflow would be to restart scanning from left+L, re-counting everything. Instead, decrementing the leftmost word and nudging left forward keeps all the still-valid counts intact — this amortization is the entire reason the window is faster than brute force. It's the same shrink-on-violation discipline as Minimum Window Substring and Longest Substring Without Repeating Characters, just operating on word-sized units instead of characters.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "barfoothefoobarman", words = ["foo","bar"]Interactive diagram
Window shrink on overflow
right=0 'bar'When a word over-fills, drop leftmost words by L until counts are valid again — amortized, not restarted.
[0, 9]C · Code with teaching comments
D · Why it works and complexityO(n · L) timeO(k · L) spaceOpen the invariant and proofExplore the proofHide the proof
Group start indices by start mod L so each alignment becomes one linear sweep, then amortize overlapping checks by shrinking the window instead of rebuilding it. The fixed word length is what makes 'one window per offset' both necessary (alignments don't mix) and sufficient (L of them cover everything).
ComplexityO(n · L) time, O(k · L) space — Each of the L offsets scans s once in steps of L; across an offset every word position is added once and removed at most once → O(n/L) word ops per offset, each O(L) for substring/hash, times L offsets ≈ O(n·L). Maps hold O(k) words → O(k·L) space.
E · Edge cases and pitfalls7words has duplicates [foo, foo], s="foofoo" — need={foo:2}; window grows to two foos, count=2=k → record 0. No overflow because need allows 2.Explore edge casesHide edge cases
Edge cases handled
words has duplicates [foo, foo], s="foofoo"need={foo:2}; window grows to two foos, count=2=k → record 0. No overflow because need allows 2.repeated word forcing shrink, e.g. words=[bar,foo,foo], s="...foofoofoo..."Third foo overflows need[foo]=2 → shrink drops the leftmost foo, sliding the window forward.s exactly k·L long and matchingSingle window per offset; offset that aligns records index 0.
Pitfalls
- Sliding by 1 character instead of L — re-introduces the brute-force redundancy and miscounts chunks.
- Only running offset 0 — misses matches that start at non-multiples of L.
- On overflow, restarting the scan from left+L instead of decrementing counts — loses the amortization.
- Forgetting to drop one word after recording a match — the window never advances past a found start.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); int k = words.length; if (k == 0) return res; int L = words[0].length();Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Stepping by 1 instead of by word length
Words are length L, so chunk boundaries only make sense at multiples of L from the start. Stepping by 1 both re-creates brute-force redundancy and slices words at the wrong offsets.
Explore the code comparisonHide the code comparison
Stepping by 1 instead of by word length
Words are length L, so chunk boundaries only make sense at multiples of L from the start. Stepping by 1 both re-creates brute-force redundancy and slices words at the wrong offsets.
Don't write this
for offset in range(L):
...
right += 1 # wrong unitWrite this instead
for offset in range(L):
...
right += L # advance by a whole word2Set instead of count map for duplicates
If words = [foo, foo], a set loses the multiplicity and a window with a single foo would wrongly satisfy membership. Use counts.
Explore the code comparisonHide the code comparison
Set instead of count map for duplicates
If words = [foo, foo], a set loses the multiplicity and a window with a single foo would wrongly satisfy membership. Use counts.
Don't write this
Set<String> need = new HashSet<>(Arrays.asList(words));
// later: if (need.contains(word)) ...Write this instead
Map<String,Integer> need = new HashMap<>();
for (String w : words) need.merge(w, 1, Integer::sum);3Not shrinking on overflow
When a word exceeds its needed count, restarting the scan loses the amortized cost guarantee. Decrement the leftmost word and advance left instead.
Explore the code comparisonHide the code comparison
Not shrinking on overflow
When a word exceeds its needed count, restarting the scan loses the amortized cost guarantee. Decrement the leftmost word and advance left instead.
Don't write this
if window[word] > need[word]:
window.clear(); count = 0; left = right # over-resets, O(n*k)Write this instead
while window[word] > need[word]:
lw = s[left:left + L]
window[lw] -= 1
left += L
count -= 1Revise
Carry the pattern into the interview
Pattern to remember
Fixed-length sliding window stepping by word length + count map
Code pattern to memorize
need = Counter(words); L = len(words[0]); k = len(words)
for offset in range(L):
slide a window of words [left, right) stepping by L
on each word: window[w]++ ; while window[w] > need[w]: drop left word
if window holds k words: record left, then drop one to keep slidingRules to remember
- 1Every word has the same length L — that's what makes a fixed-step window possible. Always state this first.
- 2Run L independent windows, one per start offset
0..L-1, so every possible word-aligned boundary is covered exactly once. - 3Step the window by L (one word), never by 1 — the building block is a word, not a character.
- 4On overflow (a word appears more than
needallows, or an unknown word), shrink/reset from the left rather than restarting the scan. - 5Order within the concatenation does not matter and there must be no gaps — count equality of the k chunks is the whole condition.
Use this pattern when
- Match a multiset of equal-length tokens as a contiguous block
- All pattern pieces share one fixed length → window can step by that length
- Anagram-of-words / permutation-of-words style matching
- You'd otherwise re-scan overlapping windows and want to amortize with a sliding count map
Choose another pattern when
- Words have different lengths → can't step by a fixed L; needs a trie / DP word-break instead
- Only one word or order matters → plain substring search (KMP)
- Need the longest such window, not exact-length blocks → different window template
- Tokens can overlap or repeat freely → not a fixed multiset match
Interview takeaway
The equal-length guarantee is the entire unlock: it turns a messy substring problem into 'slide a word-granular window and compare count maps'. The L-offset trick amortizes overlapping checks so each character is visited O(1) times per offset — O(n·L) overall, the hallmark of an interview-grade answer over the brute force.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternFixed-length sliding window stepping by word length, run once per alignment offset, with a count-map multiset comparison. Recognise it whenever you must match a multiset of equal-length tokens as a contiguous block. The equal-length guarantee enables the word-granular step; the L-offset partition plus shrink-on-overflow is what amortizes it down to O(n·L). Cousin to Minimum Window Substring and Find All Anagrams.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Minimum Window SubstringSame need/window count-map and shrink-on-satisfy idea, but on single characters and seeking the smallest window.
- Find All Anagrams in a StringComing soonFixed-length sliding window of single characters — the character-level analog of this problem.
- Permutation in StringCheck if any window is a permutation (multiset match) of a pattern — same count-map equality.
- Longest Substring Without Repeating CharactersVariable-length window shrinking on a violation — the shrink discipline used here, maximizing length.