Substring with Concatenation of All Words

Problem

You are given a string s and a list words in which every word has the same length. A concatenated substring of s is a substring that is exactly the words of words glued together in some order — each word used exactly as many times as it appears in the list, with nothing in between. Return the starting indices (in any order) of all concatenated substrings in s.

Examples

• s = "barfoothefoobarman", words = ["foo", "bar"] → [0, 9] — "barfoo" starts at 0 and "foobar" starts at 9; both are the two words in some order.
• s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"] → [] — every candidate needs "word" twice plus "good" and "best", and no window of length 16 delivers that.
• s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"] → [6, 9, 12] — "foobarthe", "barthefoo", and "thefoobar" are all permutations of the three words.

Constraints

• 1 <= len(s) <= 10^4
• 1 <= len(words) <= 5000, 1 <= len(words[i]) <= 30 — all words the same length
• s and all words consist of lowercase English letters.
• Checking every start index against every word from scratch multiplies to ~10^8 character work — the intended solutions exploit the fixed word length to do better.

Think about it first

TL;DR

Word-stride sliding window, one pass per offset — O(n · w) time (w = word length), O(k · w) space (k = number of words).

Approach 1 — Brute force (verify every start index)

Every valid window has exactly total = k * w characters, so there are at most n - total + 1 candidate starts. For each one, chop the window into k chunks of width w and check that the chunk multiset equals the word multiset, bailing out early on the first impossible chunk.

from collections import Counter
from typing import List

def findSubstring(s: str, words: List[str]) -> List[int]:
    n = len(s)
    k = len(words)
    w = len(words[0])
    total = k * w
    if total > n:
        return []
    need = Counter(words)
    result = []
    for start in range(n - total + 1):
        seen: Counter = Counter()
        j = start
        while j < start + total:
            chunk = s[j:j + w]
            if chunk not in need:
                break
            seen[chunk] += 1
            if seen[chunk] > need[chunk]:
                break
            j += w
        else:
            result.append(start)
    return result

Complexity: O((n − total + 1) · k · w) time — each start hashes up to k chunks of w characters — and O(k · w) space for the counters.

With n = 10^4 and k · w also up to ~10^4 (the window can’t exceed s), that’s on the order of 10^8 character operations; the early break helps on random data but adversarial inputs (long runs of nearly-valid windows) push it over the edge.

Approach 2 — Word-stride sliding window, one pass per offset

Because all words share one length w, a valid window can only be read as chunks starting at positions congruent to some offset r modulo w. So instead of treating s as characters, treat it as w separate streams of words: for each offset r in 0..w-1, the chunks s[r:r+w], s[r+w:r+2w], … form a sequence, and over that sequence the task becomes “find windows whose word-counts equal need” — the standard expand/shrink two-pointer window. Each incoming chunk triggers one of three actions:

1. Chunk is not a word → the window can never cross it, so reset everything past it.
2. Chunk is a word but its count now exceeds its quota → shrink from the left (whole chunks) until the excess is gone.
3. Window reaches exactly k chunks → record left, drop the leftmost chunk, and continue.

flowchart TD
    A[Next chunk enters on the right] --> B{Is it one of the words?}
    B -->|No| C[Clear window; reset count and left past this chunk]
    B -->|Yes| D[Add chunk; count + 1]
    D --> E{Its count over quota?}
    E -->|Yes| F[Drop leftmost chunk; count - 1]
    F --> E
    E -->|No| G{count equals k?}
    G -->|Yes| H[Record left; drop leftmost; slide by one word]
    G -->|No| I[Read next chunk]

Each chunk enters the window once and leaves at most once, so each offset pass is linear in its stream.

from collections import Counter
from typing import List

def findSubstring(s: str, words: List[str]) -> List[int]:
    n = len(s)
    k = len(words)
    w = len(words[0])
    if k * w > n:
        return []
    need = Counter(words)
    result = []

    for offset in range(w):
        window: Counter = Counter()
        count = 0                    # chunks currently in the window
        left = offset
        for j in range(offset, n - w + 1, w):
            chunk = s[j:j + w]
            if chunk not in need:
                window.clear()       # hard reset past the bad chunk
                count = 0
                left = j + w
                continue
            window[chunk] += 1
            count += 1
            while window[chunk] > need[chunk]:
                dropped = s[left:left + w]
                window[dropped] -= 1
                left += w
                count -= 1
            if count == k:
                result.append(left)
                dropped = s[left:left + w]
                window[dropped] -= 1   # slide by one word
                left += w
                count -= 1
    return result

Walkthrough with s = "barfoothefoobarman", words = ["foo", "bar"] (w = 3, k = 2, need = {foo:1, bar:1}):

Offset 0 — chunk stream: bar, foo, the, foo, bar, man

Offset 1 (arf, oot, hef, oob, arm) and offset 2 (rfo, oth, efo, oba, rma): no chunk is ever a word — nothing recorded.

Result: [0, 9].

Complexity: O(n · w) time — w passes, and within a pass every chunk is sliced/hashed O(w) at most twice (once entering, once leaving), giving O(n) work per pass. Space O(k · w) for the counters. With n = 10^4 and w ≤ 30, that’s ~3·10^5 chunk operations versus the brute force’s ~10^8.

Common pitfalls

• Treating words as a set: duplicates matter (["word", "good", "best", "word"] needs "word" twice), so both the target and the window must be Counters.
• Sliding by one character inside a pass instead of one word: the per-offset streams already cover all alignments; striding by 1 within a pass double-counts and breaks the counter bookkeeping.
• Forgetting the full reset on an unknown chunk — merely decrementing leaves ghost words in the window and reports false starts.
• Off-by-one in the chunk loop bound: the last chunk starts at n - w, so iterate range(offset, n - w + 1, w); using n - total + 1 here silently drops chunks the shrinking side still needs.

Pattern takeaway

When the units being matched have a uniform size, re-index the problem in units instead of characters: run one sliding-window pass per residue class of the unit length, and inside each pass apply the standard variable-window recipe (expand right; shrink left exactly while a count is over quota; emit when the window is exactly full). Turning a string problem into w independent word-stream problems is what collapses O(n · k · w) brute force into O(n · w).