30. Substring with Concatenation of All Words

HardSliding WindowSliding window + word-frequency counterWord-aligned sliding window over fixed-length tokens

Substring with Concatenation of All Words

Given a string s and an array words of strings that all have the same length, return the starting indices of every substring of s that is a concatenation of every word in words exactly once, in any order, with no characters in between.

Open official problem prompt ↗

In plain English

Find every position where s contains a back-to-back arrangement of all the given words, each used exactly once.

Picture it like this

Reading a sentence chopped into fixed-width blocks and finding where a specific bag of blocks appears in a row, in any order but with no gaps.

Example

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0, 9]
Why: "barfoo" starts at index 0 and "foobar" starts at index 9; each is a permutation of the two words.

Constraints

1 <= s.length <= 10^41 <= words.length <= 50001 <= words[i].length <= 30All words[i] have the same lengths and words[i] consist of lowercase English letters

Pattern lesson

See the pattern, then code

Word-aligned sliding window over fixed-length tokens

↗

Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. Because every word is the same length, slide the window in steps of that length starting from each of word_len offsets, keeping a running count of the words currently matched.

New words, made simpleKnow these before the algorithm

word_len: The common length of every word, and thus the stride of the window.
offset: One of word_len alignments; scanning all of them covers every possible start position.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Check each index independently

Rebuilds the whole multiset at every index, wasting the overlap between adjacent windows.

At every start index, slice the next window into words and compare the multiset to words.

Time O(m * total_words)Space O(k)

Best choiceWord-aligned sliding window

Each start position is visited once across the offset scans and each token slice costs word_len, so total work is O(m * word_len).

Group starts by offset modulo word_len and slide a running counter word by word, adjusting only at the edges.

Time O(m * word_len)Space O(k)

The rule we keep true

Invariant

Within an offset scan, the window from left to right contains only required words, each appearing no more than its required count.

Why this is correct

Reasoning

Every valid concatenation must be aligned to some offset in [0, word_len), so scanning all offsets covers all starts. Within an offset, adding a word and shrinking on surplus keeps the window a valid prefix of some concatenation; when matched equals the word count the whole multiset is present exactly, which is precisely a solution.

The algorithm in three movesSay these aloud before coding

1Compute word_len, count of words, and total window width; build the required word-frequency map

need={foo:1,bar:1}

2For each of word_len starting offsets, slide a window one word at a time

offset 0: window bar,foo matched=2 -> record 0

3Add each word; if it over-fills a required word, drop words from the left until valid; if it is not a required word, reset the window

later foo,bar matched=2 -> record 9

4When the matched count equals the number of words, record the window's start index

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

bar0

foo1

the2

foo3

bar4

man5

1 · Reads[0:3]

2 · AskIs 'bar' required and not over-filled?

3 · Update statecount={bar:1}, matched=1

4 · Resultcontinue

Key takeaway

Tokens read in steps of 3; bar+foo at index 0 and foo+bar at index 9 each match the word multiset.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-11Setup and guards
Compute stride, total width, and the required word counts; bail out early if the window cannot fit.
2
Lines 12-16Offset loop
Restart the running counter for each of word_len alignments so every start position is covered.
3
Lines 17-26Slide and adjust
Add the incoming word; shrink from the left on surplus of a required word; record a hit when all words are matched.
4
Lines 27-30Reset on foreign word
A word not in the requirement invalidates the whole window, so clear the counter and jump past it.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

words contains duplicates (the count map must honor multiplicity)
Total window width exceeds len(s) returns empty list
A required word never appears in s returns empty list
s exactly equals one concatenation returns [0]

Common beginner mistakes

Scanning only offset 0 instead of all word_len offsets
Treating words as a set and losing duplicate counts
Resetting left incorrectly after encountering a foreign word (must skip past it)
Recomputing the full multiset each step instead of adjusting incrementally

Check your understanding

Why is it enough to run only word_len separate scans instead of starting at every index?

PyPython 3 · solution.py

Optimal

1class Solution:2    def findSubstring(self, s: str, words: list[str]) -> list[int]:3        from collections import Counter4        if not s or not words:5            return []6        word_len = len(words[0])7        num_words = len(words)8        window = word_len * num_words9        if window > len(s):10            return []11        need = Counter(words)12        result = []13        for offset in range(word_len):14            left = offset15            count = Counter()16            matched = 017            for right in range(offset, len(s) - word_len + 1, word_len):18                word = s[right:right + word_len]19                if word in need:20                    count[word] += 121                    matched += 122                    while count[word] > need[word]:23                        left_word = s[left:left + word_len]24                        count[left_word] -= 125                        matched -= 126                        left += word_len27                    if matched == num_words:28                        result.append(left)29                        left_word = s[left:left + word_len]30                        count[left_word] -= 131                        matched -= 132                        left += word_len33                else:34                    count.clear()35                    matched = 036                    left = right + word_len37        return result

Time complexityO(m * word_len) where m = len(s); word_len offset scans, each slicing length-word_len tokens across the stringOptimized

Space complexityO(k) for the word countsExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMetaAdobe

Substring with Concatenation of All Words

Substring with Concatenation of All Words

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Sliding Window