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.
- Difficulty: Hard
- Topics: Strings, Hash Table, Sliding Window
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 100001 <= words.length <= 50001 <= words[i].length <= 30All words have the same length.s and words[i] consist of lowercase English letters.
Hints for Substring with Concatenation of All Words
Hint 1
Every word is the same length
w, so a valid window is exactlywords.length * wcharacters and splits cleanly intow-sized pieces.Hint 2
Build a multiset (count map) of the required words.
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
- Tally the required words into
need. - The window length is
k * w; slidestartover every position where a full window fits. - Walk the window in
w-sized steps, tallying pieces intohave; abandon the window as soon as a piece is not inneedor exceeds its required count. - Record
startwhen allkpieces 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 runswsliding 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 outJava
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