Substring with Concatenation of All Words

HardSliding Window · Hash Map🧩 Sliding Window LeetCode #30 ↗Updated Oct 30, 2026

Problem

You are given a string s and an array words in which every word has the same length. A position in s is a match if the text starting there is some ordering of all the words glued together, each word used exactly as many times as it appears in words. Return every matching start index, in any order.

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

Inputs = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]Output[]

Inputs = "barfoofoobarthefoobarman", words = ["bar","foo","the"]Output[6,9,12]

1 ≤ |s| ≤ 10⁴ · 1 ≤ words.length ≤ 5000 · 1 ≤ words[i].length ≤ 30 · lowercase letters only

Try it yourself

Java

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Because all words share length L, only L different “word grids” exist (start offsets 0..L-1). On each grid, treat whole words as the units of a sliding window with a frequency map — just like a fixed-alphabet anagram search.

PatternSliding Window

Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.

Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.

Open the Sliding Window guide →

Approaches

Brute ForceCut, Sort and Compare

Time O(n · m log m · L)Space O(m · L)

Sort a copy of words once. For every start index, cut the next m chunks of length L, sort them, and compare with the sorted words. Two multisets are equal exactly when their sorted forms are equal.

Java

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    int m = words.length, len = words[0].length();
    int total = m * len;
    String[] target = words.clone();
    Arrays.sort(target);
    for (int i = 0; i + total <= s.length(); i++) {
        String[] chunks = new String[m];
        for (int j = 0; j < m; j++) {
            chunks[j] = s.substring(i + j * len, i + (j + 1) * len);
        }
        Arrays.sort(chunks);
        if (Arrays.equals(chunks, target)) result.add(i);
    }
    return result;
}

Easy to prove correct, but sorting at every index is wasteful.

BetterCount Map with Early Exit

Time O(n · m · L)Space O(m · L)

Store how often each word is required. At every start index, read chunks one by one into a fresh “seen” map and stop the moment a chunk is unknown or exceeds its required count. Reaching m chunks means a match.

Java

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    int m = words.length, len = words[0].length();
    Map<String, Integer> need = new HashMap<>();
    for (String w : words) need.merge(w, 1, Integer::sum);
    for (int i = 0; i + m * len <= s.length(); i++) {
        Map<String, Integer> seen = new HashMap<>();
        int j = 0;
        while (j < m) {
            String chunk = s.substring(i + j * len, i + (j + 1) * len);
            int limit = need.getOrDefault(chunk, 0);
            if (seen.merge(chunk, 1, Integer::sum) > limit) break; // unknown or too many
            j++;
        }
        if (j == m) result.add(i);
    }
    return result;
}

No sorting and it bails out early, but still restarts from scratch at each index.

OptimalWord-Level Sliding Window per Offset

Time O(n · L + m · L)Space O(m · L)

For each offset 0..L-1, step right one word at a time. An unknown word resets the window past it; a word that becomes over-used makes left drop words until its count is legal again. When the window holds m words it is a match; record left and drop one word to keep sliding.

Java

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    int m = words.length, len = words[0].length(), n = s.length();
    Map<String, Integer> need = new HashMap<>();
    for (String w : words) need.merge(w, 1, Integer::sum);
    for (int offset = 0; offset < len; offset++) {
        Map<String, Integer> window = new HashMap<>();
        int left = offset, count = 0;
        for (int right = offset; right + len <= n; right += len) {
            String word = s.substring(right, right + len);
            if (!need.containsKey(word)) { // restart after an unknown word
                window.clear();
                count = 0;
                left = right + len;
                continue;
            }
            window.merge(word, 1, Integer::sum);
            count++;
            while (window.get(word) > need.get(word)) { // too many copies
                window.merge(s.substring(left, left + len), -1, Integer::sum);
                count--;
                left += len;
            }
            if (count == m) {
                result.add(left);
                window.merge(s.substring(left, left + len), -1, Integer::sum);
                count--;
                left += len;
            }
        }
    }
    return result;
}

Dry runs = "barfoothefoobarman", words = ["foo","bar"]

l left wordr right word changed

r=0
bar
l r
foo

the

foo

bar

man

count=1
r=1
bar
l
foo
r
the

foo

bar

man

count=2 → add 0
r=2
bar

foo

the
r
foo

bar

man

"the" unknown: reset
r=3
bar

foo

the

foo
l r
bar

man

count=1
r=4
bar

foo

the

foo
l
bar
r
man

count=2 → add 9
r=5
bar

foo

the

foo

bar

man
r
reset; [0,9] ✔

Every chunk enters and leaves each window once — no re-scanning.

Pro tip

Say out loud why only L offsets are needed: any match starts at some index i, and i % L picks its grid.

At a glance

Level	Approach	Time	Space
Brute Force	Cut, Sort and Compare	`O(n · m log m · L)`	`O(m · L)`
Better	Count Map with Early Exit	`O(n · m · L)`	`O(m · L)`
Optimal	Word-Level Sliding Window per Offset	`O(n · L + m · L)`	`O(m · L)`

Common pitfalls

Using a set instead of a count map — duplicate words like ["good","good"] break.
Sliding one character at a time inside a grid — chunks must be aligned to the offset.
Forgetting to drop a word after recording a match, so the window grows past m words.

Interview tips

Relate it to Find All Anagrams: same window, but the “letters” are whole words.
State the complexity in terms of n, m and L — substring hashing costs O(L).
Ask whether words can repeat; the answer drives the count-map design.

Pattern

Sliding window over tokens → find permutations of a multiset of fixed-length tokens inside a long string.

My notes saved in this browser