Substring with Concatenation of All Words

Hard
687.

Substring with Concatenation of All Words

Substring with Concatenation of All Words is a hard coding problem on strings, hash table and sliding window, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Substring with Concatenation of All Words — Solution

Substring with Concatenation of All Words solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Substring with Concatenation of All Words is a hard coding problem on strings, hash table and sliding window, asked in Amazon, Google and Meta interviews.

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.

Hints for Substring with Concatenation of All Words

  1. Hint 1

    Every word is the same length w, so a valid window is exactly words.length * w characters and splits cleanly into w-sized pieces.

  2. Hint 2

    Build a multiset (count map) of the required words.

  3. Hint 3

    For each start index, chop the window into pieces and check the counts match — bail out the moment a piece is unknown or over-used.

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

Java

public static int[] findSubstring(String s, String[] words) {
    List<Integer> out = new ArrayList<>();
    int k = words.length;
    int w = words[0].length();
    int total = k * w;
    if (s.length() < total) return new int[0];
    Map<String, Integer> need = new HashMap<>();
    for (String word : words) need.put(word, need.getOrDefault(word, 0) + 1);
    for (int start = 0; start + total <= s.length(); start++) {
        Map<String, Integer> have = new HashMap<>();
        boolean ok = true;
        for (int t = 0; t < k; t++) {
            String piece = s.substring(start + t * w, start + (t + 1) * w);
            Integer req = need.get(piece);
            if (req == null) { ok = false; break; }
            int c = have.getOrDefault(piece, 0) + 1;
            have.put(piece, c);
            if (c > req) { ok = false; break; }
        }
        if (ok) out.add(start);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < out.size(); i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> findSubstring(string s, vector<string>& words) {
    vector<int> out;
    int k = (int) words.size();
    int w = (int) words[0].size();
    int total = k * w;
    if ((int) s.size() < total) return out;
    unordered_map<string, int> need;
    for (const string& word : words) need[word]++;
    for (int start = 0; start + total <= (int) s.size(); start++) {
        unordered_map<string, int> have;
        bool ok = true;
        for (int t = 0; t < k; t++) {
            string piece = s.substr(start + t * w, w);
            auto it = need.find(piece);
            if (it == need.end()) { ok = false; break; }
            int c = ++have[piece];
            if (c > it->second) { ok = false; break; }
        }
        if (ok) out.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets