Get started

Substring with Concatenation of All Words — Hard Problem & Solution

All strings in words have the same length. A concatenated substring of s is a substring made by joining every word of words exactly once, in any order and…

Problem statement

All strings in words have the same length. A concatenated substring of s is a substring made by joining every word of words exactly once, in any order and with nothing in between.

Return the starting indices of all concatenated substrings, in increasing order.

Example 1

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: "barfoo" starts at 0 and "foobar" at 9.

Example 2

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: No window holds two words and one each of good and best.

Example 3

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

Constraints

  • 1 <= s.length <= 10000
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • All words have the same length.
  • s and words[i] consist of lowercase English letters.

How to solve Substring with Concatenation of All Words

Equal word lengths make the window's decomposition unique: slice it into w-character pieces and compare the resulting multiset against the required one.

Approach

  1. Tally the required words into need.
  2. The window length is k * w; slide start over every position where a full window fits.
  3. Walk the window in w-sized steps, tallying pieces into have; abandon the window as soon as a piece is not in need or exceeds its required count.
  4. Record start when all k pieces pass.

Why it works

Because the concatenation uses each word exactly once and all words are the same length, a window is valid precisely when its piece multiset equals need — and checking 'no piece over its quota' across exactly k pieces is equivalent to multiset equality.

Complexity

  • Time — O(n · k)
  • Space — O(total word length)

Pitfalls

  • Using a set rather than a count map accepts a window that repeats one word and omits another.
  • Checking have[piece] > need[piece] is what lets the early exit be correct — without it, a duplicate slips through.
  • The O(n · w) refinement runs w sliding windows, one per offset class, instead of restarting at each index.

Reference solution

Python

from typing import List

def findSubstring(s: str, words: List[str]) -> List[int]:
    k = len(words)
    w = len(words[0])
    total = k * w
    need = {}
    for word in words:
        need[word] = need.get(word, 0) + 1
    out = []
    for start in range(0, len(s) - total + 1):
        have = {}
        ok = True
        for t in range(k):
            piece = s[start + t * w: start + (t + 1) * w]
            if piece not in need:
                ok = False
                break
            have[piece] = have.get(piece, 0) + 1
            if have[piece] > need[piece]:
                ok = False
                break
        if ok:
            out.append(start)
    return out

JavaScript

var findSubstring = function(s, words) {
    var out = [];
    var k = words.length;
    if (k === 0) return out;
    var w = words[0].length;
    var total = k * w;
    if (s.length < total) return out;
    var need = {};
    for (var i = 0; i < k; i++) {
        need[words[i]] = (need[words[i]] === undefined ? 0 : need[words[i]]) + 1;
    }
    for (var start = 0; start + total <= s.length; start++) {
        var have = {}, ok = true;
        for (var t = 0; t < k; t++) {
            var piece = s.substr(start + t * w, w);
            if (need[piece] === undefined) { ok = false; break; }
            have[piece] = (have[piece] === undefined ? 0 : have[piece]) + 1;
            if (have[piece] > need[piece]) { ok = false; break; }
        }
        if (ok) out.push(start);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue