Top Interview 150
The Substring with Concatenation of All Words problem is a challenging sliding window and hash map problem. Letโs break it down step by step to solve it efficiently.
๐ Problem Description
Given a string s
and an array of strings words
:
- Each word in
words
is of the same length. - A valid concatenated substring is a substring of
s
that contains all the strings fromwords
concatenated in any order. - Return an array of the starting indices of all such substrings in
s
.
๐ก Examples
Example 1
Input: s = "barfoothefoobarman", words = ["foo", "bar"]
Output: [0, 9]
Explanation: Substrings starting at indices 0 and 9 are "barfoo" and "foobar".
Example 2
Input: s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"]
Output: []
Explanation: No valid concatenation exists.
Example 3
Input: s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"]
Output: [6, 9, 12]
Explanation: Substrings at indices 6, 9, and 12 are valid concatenations.
๐ JavaScript Solution
To solve this problem efficiently:
- Use a sliding window approach to examine substrings of the same length as the concatenated words.
- Use a hash map to count the occurrences of each word in
words
.
Implementation
var findSubstring = function(s, words) {
const wordLength = words[0].length;
const wordCount = words.length;
const totalLength = wordLength * wordCount;
const wordFrequency = {};
for (let word of words) {
wordFrequency[word] = (wordFrequency[word] || 0) + 1;
}
const result = [];
for (let i = 0; i < wordLength; i++) {
let left = i, right = i;
let windowFrequency = {};
let count = 0;
while (right + wordLength <= s.length) {
const word = s.substring(right, right + wordLength);
right += wordLength;
if (wordFrequency[word] !== undefined) {
windowFrequency[word] = (windowFrequency[word] || 0) + 1;
if (windowFrequency[word] <= wordFrequency[word]) {
count++;
}
while (windowFrequency[word] > wordFrequency[word]) {
const leftWord = s.substring(left, left + wordLength);
windowFrequency[leftWord]--;
if (windowFrequency[leftWord] < wordFrequency[leftWord]) {
count--;
}
left += wordLength;
}
if (count === wordCount) {
result.push(left);
}
} else {
windowFrequency = {};
count = 0;
left = right;
}
}
}
return result;
};
๐ How It Works
-
Precompute Word Frequencies:
- Build a hash map
wordFrequency
to store the count of each word inwords
.
- Build a hash map
-
Sliding Window:
- Slide a window of size
totalLength
(length of all concatenated words) across the strings
. Use a secondary hash mapwindowFrequency
to count occurrences of words within the current window.
- Slide a window of size
-
Shrink or Expand Window:
- If a word occurs too many times, shrink the window from the left.
- If all words match, record the starting index.
๐ Complexity Analysis
-
Time Complexity:
O(nโ k)
, where:-
n
is the length of the string s. -
k
is the length of each word in words. - Each character is processed at most once due to the sliding window.
-
-
Space Complexity:
O(m+k)
, where:-
m
is the number of unique words in words. -
k
is the number of words in words.
-
๐ Dry Run
Input: s = "barfoothefoobarman"
, words = ["foo", "bar"]
Output: [0, 9]
โจ Pro Tips for Interviews
-
Clarify Constraints:
- Are all words the same length?
- Can words contain duplicates?
-
Explain Sliding Window:
- Highlight why reducing the window avoids unnecessary reprocessing.
-
Discuss Edge Cases:
- Empty string or empty words.
- Words longer than
s
.
๐ Learn More
Check out the full explanation and code walkthrough on my previous Dev.to post:
๐ Longest Substring Without Repeating Characters - JavaScript Solution
Whatโs your preferred method to solve this problem? Letโs discuss! ๐

Top comments (1)
Follow Me on GitHub ๐
If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.
Don't forget to follow for more updates!
Some comments may only be visible to logged-in visitors. Sign in to view all comments.