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

class Solution:
    def findSubstring(self, 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

The insight: 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 over which this becomes exactly a “find windows whose word-counts equal need” problem, solvable with the classic expand/shrink two-pointer window. Three events per incoming chunk:

1. Chunk not a word at all → the window can never cross it: 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 disappears.
3. Window reaches exactly k chunks → record left, then drop the leftmost chunk and continue.

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

class Solution:
    def findSubstring(self, 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).