Substring with Concatenation of All Words

Equal-width tokens turn a permutation problem into a finite set of aligned frequency windows.

Read the exact contract

Let:

• w be the common length of every word.
• m be len(words).
• total_length = m * w.

A valid answer starts at an index where the next total_length characters can be split into exactly m adjacent chunks of length w. Those chunks must contain the same multiset as words.

That contract has four consequences:

1. Word order does not matter.
2. Duplicate words do matter.
3. Chunks must be adjacent, with no intervening characters.
4. Valid matches may overlap.

The algorithm follows directly:

1. Count how many copies of each word are required.
2. Scan s in the w possible token alignments.
3. Move through each alignment one complete word at a time.
4. Reset when a chunk is unknown.
5. Shrink from the left when a known word appears too many times.
6. Record the left boundary when the repaired window contains exactly m words.

This is a fixed word length sliding window. The window moves in token-sized steps, not character-sized steps.

Why permutations and character windows miss the structure

Generating every permutation is the wrong abstraction. The problem allows any order, so order is noise. Duplicate words also make permutation generation wasteful because repeated values create equivalent arrangements.

A more reasonable baseline examines every possible character start, splits the candidate substring into m chunks, and compares its frequency map with the required map. That is correct, but it rebuilds nearly the same state for neighboring starts.

The useful recognition signal is narrower:

• every token has the same width;
• validity depends on exact token multiplicities;
• the tokens occupy one contiguous interval.

A set cannot represent the contract. For example:

words = ["word", "good", "best", "word"]

requires two copies of "word". A set would collapse those two requirements into one.

A frequency map preserves the actual obligation:

required["word"] == 2
required["good"] == 1
required["best"] == 1

The optimized scan reuses work. Each token enters a window once, and each token later leaves through the left boundary at most once.

Split the scan into fixed alignments

Suppose w = 3. Starting at offset 0, the token stream is:

s[0:3], s[3:6], s[6:9], s[9:12], ...

Starting at offset 1 gives:

s[1:4], s[4:7], s[7:10], s[10:13], ...

Starting at offset 2 gives:

s[2:5], s[5:8], s[8:11], s[11:14], ...

There are exactly w streams: offsets 0 through w - 1.

Every possible substring start belongs to exactly one stream because every integer index has one remainder modulo w. If the start is i, its alignment is i % w.

This decomposition gives the algorithm two guarantees:

• no candidate alignment is missed;
• both pointers can advance by w without breaking token boundaries.

Within one alignment:

• right points to the next token to read;
• left points to the first token currently in the window;
• window_count is the number of complete tokens between them.

A window can match only when:

window_count == m

At that point its character length is automatically m * w.

Derive the frequency-window invariant

Build one map for the target:

required[word] = the number of copies needed

For the current aligned interval, maintain:

seen[word] = the number of copies currently present
window_count = the number of complete tokens in the window

The key condition is:

After repair, the window is aligned, contains only required words, and every seen[word] is at most required[word].

There is an important timing detail here. Immediately after adding a known token, the newest token may temporarily violate its frequency bound. The invariant is restored by the repair loop. Only after that loop is it safe to test window_count == m.

Unknown token: reset the stream

If the next token is not in required, no valid concatenation can cross it. Clear the current state and start after that token:

seen.clear()
window_count = 0
left = right

The previous suffix is unusable because every candidate window crossing the unknown token would contain an invalid word.

This is a hard boundary, not an excess-count problem.

Excess known token: discard a prefix

If the new token is known but its count is now too large, remove complete tokens from the left until the newest token is legal again.

removed = s[left:left + word_length]
left += word_length
window_count -= 1

The left pointer must move by word_length. Removing one character would destroy the alignment and make the frequency map describe a different partition from the pointers.

Why is it sufficient to check the newest token?

Before insertion, the repaired window already satisfies every upper bound. Inserting one token changes only that token's count. Therefore, immediately after insertion, only the newest token can be excessive. Removing from the left may pass through other words, but it needs to continue only until the newest token's count falls within its bound.

Full window: record without resetting

After repair, if:

window_count == m

then the window contains m required tokens and no frequency exceeds its target. Its frequency multiset must therefore equal the target multiset. Record left.

Do not clear the window after recording. The next token may create another valid window that overlaps the current one.

The algorithm is a conveyor belt: record a valid segment, then keep the belt moving.

Dry-run the failure modes

Repeated words and oversized windows

Consider:

s = "wordgoodgoodgoodbestword"
words = ["word", "good", "best", "word"]

The required counts are:

word: 2
good: 1
best: 1

For the alignment beginning at 0, the token stream is:

word, good, good, good, best, word

After reading the first two tokens:

seen = {"word": 1, "good": 1}
window_count = 2

The next "good" makes its count exceed the allowed one. The repair loop removes from the left:

1. Remove "word".
2. "good" is still excessive.
3. Remove the first "good".
4. The newest "good" is now legal.

The algorithm did not restart the scan. It discarded only the shortest invalid prefix. That distinction matters: an excess token usually means “move left,” not “throw away everything.”

The final result is empty because no repaired four-token window has the required multiplicities.

Overlapping matches

Now consider:

s = "barfoofoobarthefoobarman"
words = ["bar", "foo", "the"]

For offset 0, the relevant token stream is:

bar, foo, foo, bar, the, foo, bar, man

The first three tokens produce:

bar, foo, foo

The second "foo" is excessive. Remove "bar" and then the older "foo". The repaired window is:

foo

Continue reading:

foo, bar, the

At index 6, the window is:

foo, bar, the

Record 6, but keep the window.

The next token is "foo". It becomes excessive, so remove the leftmost "foo". The window becomes:

bar, the, foo

Record 9.

The next token is "bar". Remove the older "bar":

the, foo, bar

Record 12.

The result is:

[6, 9, 12]

Resetting after the match at 6 would lose the suffix that begins the match at 9. Overlap is not an exceptional case here; it is a direct consequence of continuing the repaired window.

Unknown tokens and incomplete tails

An unknown complete token is a hard boundary. For example, if the stream contains:

foo, bar, xyz, foo

and "xyz" is not required, the window before it cannot contribute to a match after it. Clear the state and restart at the next token.

A trailing fragment shorter than w is different. It is not a token at all, so the loop must stop before extracting it:

while right + word_length <= len(s):

Common implementation failures follow from confusing these cases:

• using a set instead of a frequency map;
• moving pointers one character at a time;
• shrinking by characters instead of whole tokens;
• retaining an unknown token in the window;
• allowing an excessive word to remain in seen;
• clearing the window after every match;
• treating an incomplete tail as a candidate token.

Prove the algorithm correct

Alignment coverage

The outer loop checks every offset from 0 through w - 1.

Any candidate start i has exactly one remainder i % w, so it belongs to exactly one alignment. Within that alignment, right visits every complete word-sized chunk beginning at that remainder.

Therefore every possible candidate start is covered exactly once by the alignment decomposition.

Invariant preservation

At the start of an iteration, the current window is aligned and repaired.

• If the incoming token is unknown, the algorithm clears the state and sets left = right. The new window is empty and valid.
• If the token is known, it is added to seen.
• The insertion can violate only the newest token's upper bound.
• The repair loop removes complete tokens from the left until that bound is restored.
• Every pointer movement is a multiple of w, so alignment remains intact.

After repair, the window contains only required tokens and respects every multiplicity bound.

Soundness

Suppose the repaired window contains exactly m tokens.

Every token is required, and no required frequency is exceeded. The window has the same total number of tokens as words.

If one required word appeared fewer times than required, some other word would have to appear more times to keep the total at m. That would violate an upper bound. Therefore every frequency matches exactly, and left is a valid answer.

Completeness

Take any valid concatenation. Its chunks all have width w, contain only required words, and respect every required multiplicity.

When the scan reaches those chunks in their alignment stream:

• no unknown token resets the window;
• no chunk creates an invalid frequency excess within the target segment;
• the window reaches m tokens.

The scan records the start.

The left boundary may already have advanced because of an earlier excess before this valid suffix began. That is exactly what completeness needs: the window does not have to start at the beginning of the alignment stream. It only has to preserve the valid suffix currently under consideration.

Equal word length is the structural reason this proof works. With unequal word lengths, there is no single token width, no finite modulo-w alignment decomposition, and no direct reason that both pointers can advance by one common amount.

Implement the Python solution

from collections import Counter


def find_substring(s: str, words: list[str]) -> list[int]:
    if not s or not words or not words[0]:
        return []

    word_length = len(words[0])
    word_count = len(words)
    total_length = word_length * word_count

    if total_length > len(s):
        return []

    required = Counter(words)
    result = []

    for offset in range(word_length):
        left = offset
        right = offset
        window_count = 0
        seen = Counter()

        while right + word_length <= len(s):
            word = s[right:right + word_length]
            right += word_length

            if word not in required:
                seen.clear()
                window_count = 0
                left = right
                continue

            seen[word] += 1
            window_count += 1

            # The newest word may be excessive here.
            # After this loop, the full invariant is restored.
            while seen[word] > required[word]:
                removed = s[left:left + word_length]
                seen[removed] -= 1

                if seen[removed] == 0:
                    del seen[removed]

                left += word_length
                window_count -= 1

            # This check is valid only after repair.
            if window_count == word_count:
                result.append(left)

    return result

Each variable has one obligation:

• required stores the target multiset.
• seen stores frequencies in the current repaired window.
• left and right define an aligned interval.
• window_count counts complete tokens in that interval.
• offset selects one of the finite alignment streams.
• result stores every certified start without changing the scan state.

The operation order is part of the proof:

1. Extract one complete token.
2. Reset if it is unknown.
3. Add it to seen.
4. Repair any excess by removing whole tokens.
5. Test whether the repaired window contains exactly word_count tokens.

The code never compares the two complete maps when it records a result. The invariant has already performed that comparison incrementally.

Verify state before trusting the output

For a debug run or an interview explanation, inspect the state after each loop iteration.

After an unknown-token reset, verify:

left == right
window_count == 0
seen is empty

After a known-token repair, verify:

right - left == window_count * word_length
sum(seen.values()) == window_count
seen[word] <= required[word] for every word in seen

The third condition applies after repair, not immediately after insertion. That transient distinction is where many off-by-one and stale-count bugs hide.

When window_count == word_count, the repaired-state checks are enough to certify a match. When a match is recorded, do not expect left or seen to reset; the next iteration may repair the window into an overlapping answer.

Analyze cost and boundaries

Let:

• n = len(s);
• m = len(words);
• w be the common word length;
• d be the number of distinct required words.

Across all alignments, each complete token position is processed once by a right pointer, and each processed token leaves through a left pointer at most once. Hash-map operations are expected constant time.

If extracting a word is treated as bounded because w is bounded, the time complexity is:

O(n)

Python string slicing copies the extracted characters. Counting that literal copy cost gives:

O(n * w)

With the stated bound on word length, this is still linear in n for the problem's input model.

Auxiliary space is:

O(d)

required stores the distinct target words, and seen stores words currently present in the repaired window. Including the output list, total space is:

O(d + r)

where r is the number of returned indices.

Test the implementation against:

• one word;
• all words identical;
• duplicate requirements mixed with distinct words;
• no matching substring;
• an unknown token in the middle;
• len(s) < m * w;
• a trailing fragment shorter than w;
• matches in several alignments;
• overlapping matches such as [6, 9, 12];
• an excessive token that requires removing several words from the left.

The transferable recognition rule is compact:

When a problem requires an exact multiset of adjacent equal-width tokens, enumerate the finite alignments, maintain bounded frequencies, reset at unknown tokens, repair excess tokens from the left, and record a full window only after the repaired invariant certifies it.