Substring with Concatenation of All Words — Multi-Lane Sliding Window

Problem Statement#

Given a string s and an array words (all words have equal length), return the start indices of every substring of s that is a concatenation of every word exactly once, in any order.

Constraints:

• 1 <= s.length <= 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• s and words[i] are lowercase English letters.

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

Input:  s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6, 9, 12]

Why This Problem Matters#

LeetCode 30 — Substring with Concatenation of All Words — is a Hard regularly seen at Google, Amazon, and Meta. The brute force O(n * total) where total is wlen * wcount is too slow for the upper bounds. The interview-level solution treats the string as a sequence of fixed-length tokens and runs wlen independent sliding windows, one per word-aligned offset.

The technique is a strict generalisation of the character sliding window (LC 76, LC 438, LC 567). Mastering LC 30 means mastering token-level sliding windows with frequency maps, the gold standard for any "set of equal-length patterns" problem.

It also rewards careful bookkeeping: handling unknown tokens, duplicate words, and the formed counter cleanly is exactly the kind of attention to detail interviewers grade.

The Core Insight#

All words share length wlen. Any valid start index i falls in one of wlen lanes determined by i % wlen. Within a single lane every position is word-aligned, so we can slide by exactly one word at a time.

For each lane, walk a sliding window. Maintain need (target counts) and have (current counts). Keep a formed integer that increments when a word's count first matches its requirement and decrements when it falls below. Whenever a word appears too many times, shrink from the left a word at a time. Whenever an unknown word appears, reset everything past it.

Across all wlen lanes the total number of word reads is n / wlen * wlen = n. Each read costs O(wlen) for the slice, so the overall time is O(n * wlen) — far below the brute force O(n * wlen * wcount).

Visual Dry Run#

s = "barfoothefoobarman", words = ["foo", "bar"]. wlen = 3, total = 6.

Lane offset = 0, walking words at indices 0, 3, 6, 9, 12, 15:

Lanes 1 and 2 produce no records. Final answer: [0, 9].

Solution (Optimal)#

from collections import Counter
 
class Solution:
    def findSubstring(self, s, words):
        if not s or not words:
            return []
 
        wlen = len(words[0])
        wcount = len(words)
        total = wlen * wcount
        need = Counter(words)
        res = []
 
        for off in range(wlen):
            have = Counter()
            formed = 0
            left = off
 
            for right in range(off, len(s) - wlen + 1, wlen):
                w = s[right : right + wlen]
 
                if w in need:
                    have[w] += 1
                    if have[w] == need[w]:
                        formed += 1
 
                    while have[w] > need[w]:
                        lw = s[left : left + wlen]
                        if have[lw] == need[lw]:
                            formed -= 1
                        have[lw] -= 1
                        left += wlen
 
                    if formed == len(need) and right - left + wlen == total:
                        res.append(left)
                else:
                    have.clear()
                    formed = 0
                    left = right + wlen
 
        return res

var findSubstring = function(s, words) {
    if (!s || words.length === 0) return [];
 
    const wlen = words[0].length;
    const wcount = words.length;
    const total = wlen * wcount;
 
    const need = new Map();
    for (const w of words) need.set(w, (need.get(w) || 0) + 1);
 
    const res = [];
 
    for (let off = 0; off < wlen; off++) {
        const have = new Map();
        let formed = 0;
        let left = off;
 
        for (let right = off; right <= s.length - wlen; right += wlen) {
            const w = s.slice(right, right + wlen);
 
            if (need.has(w)) {
                have.set(w, (have.get(w) || 0) + 1);
                if (have.get(w) === need.get(w)) formed++;
 
                while (have.get(w) > need.get(w)) {
                    const lw = s.slice(left, left + wlen);
                    if (have.get(lw) === need.get(lw)) formed--;
                    have.set(lw, have.get(lw) - 1);
                    left += wlen;
                }
 
                if (formed === need.size && right - left + wlen === total) {
                    res.push(left);
                }
            } else {
                have.clear();
                formed = 0;
                left = right + wlen;
            }
        }
    }
 
    return res;
};

Time: O(n * wlen) — wlen lanes, each O(n / wlen) words, each slice is O(wlen). Space: O(wcount) for the frequency maps.

Common Mistakes#

• Sliding by one character instead of wlen, breaking word alignment.
• Running only the lane with offset 0 and missing matches at other offsets.
• Failing to reset on unknown words, dragging stale counts into the next window.
• Comparing formed to wcount instead of len(need) when duplicates exist.
• Recording right as the answer instead of left.

Interview Tips#

• State up front: "All words share length wlen, so I run wlen independent windows."
• Discuss formed carefully; it should track when a word's count exactly equals its requirement.
• Mention that the algorithm degrades gracefully when words have many duplicates because the shrink loop respects them.
• Hint at the rolling hash optimisation as a stretch goal but stick with the HashMap version for clarity.

Follow-up Questions#

• Words of different lengths? Use Aho-Corasick or suffix automaton instead.
• Can you achieve O(n) total? Replace string slicing with a rolling hash.
• Optional words? Different problem; needs variable-count matching.
• Minimum window containing every word? That is LC 76 lifted to word granularity.
• Streaming s? Maintain wlen independent state machines and emit indices as words arrive.

Key Takeaways#

• LeetCode 30 is a Hard asked at Google, Amazon, and Meta.
• All words share length wlen, so the string splits into wlen independent lanes.
• Use formed to count words whose current count exactly matches the requirement.
• Reset the window when an unknown word appears.
• Total time is O(n * wlen); space is O(wcount).
• Always compare formed to len(need) to handle duplicate words correctly.
• The pattern generalises LC 76, LC 438, and LC 567 from characters to tokens.