Substring with Concatenation of All Words

Given a string s and a list of words words, return all starting indices of substrings in s that are a concatenation of every word exactly once (in any order) with no intervening characters. All words have the same length.

Brute force checks each start with O(n * k) scanning. A sliding window by word length can do this in near-linear time.

Why this is worth learning

Equal word length turns character positions into several independent token streams. Each offset modulo wordLen needs its own sliding window.

Before coding: one-minute experiment

For s="barfoofoo" and words=["foo","bar"], why does start 0 match but start 3 fail?

Function signature

func FindSubstring(s string, words []string) []int

Inputs / outputs

• s: the search string.
• words: list of words (all same length).
• Return: starting indices of valid concatenations.

Example

s = "barfoothefoobarman"
words = ["foo","bar"]
Output: [0,9]

Constraints

• 0 <= len(s) <= 100_000
• 0 <= len(words) <= 5000
• All words have equal length.

Core idea (near-solution)

Treat s as a sequence of fixed-length words (size wordLen). Use a sliding window that moves in steps of wordLen.

For each offset in [0, wordLen-1]:

• Maintain a count map for the current window.
• If a word appears too many times, move the left side forward by one word at a time.
• When the window contains exactly len(words) words with valid counts, record the start.

Invariant: the window always contains whole words (aligned to wordLen), and counts never exceed the required frequency for any word.

Algorithm (step-by-step)

1. If words is empty, return empty.
2. Compute wordLen and wordCount. If wordLen == 0, return empty. If wordCount > len(s)/wordLen, the full concatenation cannot fit, so return empty.
3. Build a frequency map need for words.
4. For each offset from 0 to wordLen-1:
   • Set left = offset, count = 0, and clear window map.
   • For right from offset to len(s)-wordLen in steps of wordLen:
     • Read word = s[right:right+wordLen].
     • If word is not in need: reset the window and token count, set left = right + wordLen, and continue to the next complete token.
     • Else increment its count; if count exceeds need, shrink from left until valid.
     • If count == wordCount, record left and then move left by one word.
5. Return all recorded indices.

Correctness sketch

Within one offset, each step consumes one complete token. A token absent from the required dictionary cannot belong to a valid concatenation, so clearing the active window after it discards only impossible starts. For a known token whose count is excessive, remove leftmost tokens until its count is allowed again. All retained token counts are then at most their required multiplicities. If the retained token count equals the number of required words, those coordinate-wise bounds force exact equality of every multiplicity, so the start is valid. Every character start belongs to exactly one offset, and its token-aligned window is considered there. Overlapping answers remain discoverable after removing the leftmost token of a found match.

Trace (hand walkthrough)

Example input:
s = "barfoothefoobarman"
words = ["foo","bar"]
Output: [0,9]

Walk:
- wordLen=3, totalLen=6
- index 0: "barfoo" -> {bar,foo} matches -> add 0
- index 3: "foothe" no; index 6: "thefoo" no
- index 9: "foobar" matches -> add 9

Pitfalls to avoid

• Moving by one byte inside a token stream while still treating its entries as whole words. Every possible byte start is covered by the separate offset scans.
• Forgetting to reset when encountering a word not in need.
• Not handling duplicate words in words.

Debugging lens

Test repeated dictionary words, a foreign token between matches, multiple offsets, and overlaps. Resetting a map with capacity len(words) at every foreign token wastes work; a fresh unhinted map avoids that repeated preallocation.

Complexity

Let N=len(s), K=len(words), L=word length, and U=number of distinct words. Expected time is O(N·L+K·L) when string hashing/equality costs O(L); for fixed L this is linear in N+K. Auxiliary live counting space is O(U), plus O(z) result indices. Empty inputs and L=0 return immediately.

Implementation notes (Go)

• Slide in steps of wordLen and maintain counts in a map.
• Move the left pointer in word-sized steps when a count exceeds its limit.

Contract precision

All words have the same length. Empty words list, empty text, or zero word length returns an empty result in this pack. Starts are emitted grouped by offset modulo word length, not necessarily globally sorted; callers/tests must not require sorted output.

Reconstruction checkpoint

For s="barfoofoo" and words=["foo","bar"], why does start 0 match but start 3 fail?

Return to Sliding Window · Module quiz