30. Substring with Concatenation of All Words (Hard)

Problem

Given a string s and a list words, return every starting index where a substring is made from all the words in any order. Each word must appear exactly as many times as it appears in words, and every word has the same length.

Examples

s = "barfoothefoobarman", words = ["foo", "bar"] returns [0, 9]. The matching windows are "barfoo" and "foobar".
s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"] returns []. The text never supplies the second required "word" inside one window.
s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"] returns [6, 9, 12].

Constraints

1 <= s.length <= 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 30
s and every word contain lowercase English letters.

LeetCode 30 · Link · Hard

Try it yourself

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Recount every candidate window

The total candidate length is fixed: words.length * words[0].length. Start at every character where that full window fits, split the window into word-sized pieces, and compare its frequency map with the required frequencies.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
        let text = Array(s)
        let wordLength = words[0].count
        let windowLength = wordLength * words.count
        let required = frequencies(words)
        guard windowLength <= text.count else { return [] }
        var answer: [Int] = []

        for start in 0...(text.count - windowLength) {
            var seen: [String: Int] = [:]
            for offset in stride(from: 0, to: windowLength, by: wordLength) {
                let word = String(text[(start + offset)..<(start + offset + wordLength)])
                seen[word, default: 0] += 1
            }
            if seen == required { answer.append(start) }
        }
        return answer
    }

    private func frequencies(_ words: [String]) -> [String: Int] {
        words.reduce(into: [:]) { $0[$1, default: 0] += 1 }
    }
}

Let n be the length of s, m the number of words, and k the length of each word.

Time: $O(n \cdot m \cdot k)$ character work. Each candidate rebuilds a map from m slices of length k.
Space: $O(m \cdot k)$ for the distinct word keys and counts, excluding the result. Swift also uses $O(n)$ space for its character array.

This is correct, but neighboring candidates repeat almost all the same counting work.

Approach 2: Slide through word-aligned lanes

A valid match can begin at any character, but once its start offset modulo k is fixed, every word boundary in that match is fixed too. Process the k possible offsets as independent lanes:

Move right by one whole word at a time.
Reset the lane when the new chunk is not required.
If a required word becomes overrepresented, move left by whole words until its count is valid again.
When the window contains exactly m words, record left, then remove one word so overlapping matches remain possible.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
        let text = Array(s)
        let wordLength = words[0].count
        let required = frequencies(words)
        var answer: [Int] = []

        for offset in 0..<min(wordLength, text.count) {
            var left = offset
            var used = 0
            var window: [String: Int] = [:]
            var right = offset

            while right + wordLength <= text.count {
                let word = String(text[right..<(right + wordLength)])
                right += wordLength

                guard let limit = required[word] else {
                    window.removeAll(keepingCapacity: true)
                    used = 0
                    left = right
                    continue
                }

                window[word, default: 0] += 1
                used += 1
                while window[word, default: 0] > limit {
                    let outgoing = String(text[left..<(left + wordLength)])
                    window[outgoing, default: 0] -= 1
                    used -= 1
                    left += wordLength
                }

                if used == words.count {
                    answer.append(left)
                    let outgoing = String(text[left..<(left + wordLength)])
                    window[outgoing, default: 0] -= 1
                    used -= 1
                    left += wordLength
                }
            }
        }
        return answer.sorted()
    }

    private func frequencies(_ words: [String]) -> [String: Int] {
        words.reduce(into: [:]) { $0[$1, default: 0] += 1 }
    }
}

Time: $O(m \cdot k + n \cdot k + r \log r)$ , where r is the number of matches. Building the required counts takes $O(m \cdot k)$ . Across all lanes, the scan performs $O(n)$ hash-map operations, each involving a word of length k. These implementations sort the matching indices before returning them, adding $O(r \log r)$ .
Space: $O(m \cdot k + r)$ for the word counts, result, and sorting workspace. Swift also uses $O(n)$ space for its character array.

Walkthrough

For s = "barfoofoobarthefoobarman" and three-letter words, consider the lane starting at offset 0:

Chunk entering	Window after adjustment	Result
`bar`	`[bar]`	Not full yet.
`foo`	`[bar, foo]`	Not full yet.
`foo`	`[foo]`	`foo` was overused, so remove `bar` and the older `foo`.
`bar`	`[foo, bar]`	Not full yet.
`the`	`[foo, bar, the]`	Record index `6`.
`foo`	`[bar, the, foo]`	Record index `9`.
`bar`	`[the, foo, bar]`	Record index `12`.

Offsets 1 and 2 form their own lanes and produce no matches.

How to recognize this pattern

Look for all three signals:

The answer concerns contiguous substrings.
Every token has the same fixed width.
The required tokens form a multiset, so duplicate counts matter.

The equal-width rule is the giveaway. It turns an apparent permutation problem into a small number of aligned sliding-window scans. A character-frequency window is not enough because word boundaries and whole-word multiplicities define validity.

Key takeaways

Treat words as a frequency map, not a set. Duplicate requirements are part of the contract.
Split the string into k alignment lanes instead of advancing a word-based window one character at a time.
An unknown word invalidates the whole current lane window.
An overused known word only requires shrinking until that word’s count is legal again.
After recording a match, advance by one word to preserve overlapping matches.

567. Permutation in String, the fixed-width character-frequency version.
76. Minimum Window Substring, a variable-width coverage window.
3. Longest Substring Without Repeating Characters, a variable window that shrinks on duplicate state.

Sliding window, maintaining reusable state across neighboring ranges.
Hash map counting, representing required and observed multiplicities.
Two pointers, the monotonic movement behind each aligned lane.