This content originally appeared on DEV Community and was authored by Rahul Kumar Barnwal
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
wordsis of the same length. - A valid concatenated substring is a substring of
sthat contains all the strings fromwordsconcatenated 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
wordFrequencyto 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 mapwindowFrequencyto 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:-
nis the length of the string s. -
kis 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:-
mis the number of unique words in words. -
kis 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! 🚀
This content originally appeared on DEV Community and was authored by Rahul Kumar Barnwal
Rahul Kumar Barnwal | Sciencx (2025-01-05T13:32:02+00:00) LeetCode Challenge 30: Substring with Concatenation of All Words – JavaScript Solution 🚀. Retrieved from https://www.scien.cx/2025/01/05/leetcode-challenge-30-substring-with-concatenation-of-all-words-javascript-solution-%f0%9f%9a%80/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.