Substring with Concatenation of All Words solution and explanation
Google
Infosys
9 more videos on this problem
Substring with Concatenation of All Words | Leetcode #30Techdose · 13:41 · 45K views
Leetcode 30 Substring with Concatenation of All Words | Checkout SDE preparation Sheet link belowCoding Decoded · 15:32 · 28K views
30. Substring with Concatenation of All Words (Leetcode Hard)Programming Live with Larry · 27:45 · 7K views
Substring with Concatenation of All Words Python Solution - LeetCode #30Professor Oakes · 10:20 · 6K views
leetCode 30 Substring with Concatenation of All Words | JavaScript & AlgorithmJSer · 24:01 · 2K views
LeetCode Hard | 30. Substring with Concatenation of All Words | AnimationCwkscAlgo · 0:52 · 2K views
#day31 | 30. Substring with Concatenation of All Words | Hard | Top Interview 150 | Leetcode - 30Coding with Ankita · 24:28 · 2K views
Fastest Solution for Substring with Concatenation of All WordsMaximize Your Software Engineering Career · 10:18 · 1K views
P32 | 30. Substring with Concatenation of All Words | Leetcode | Top Interview 150Technosier · 16:45 · 1K views
30. Substring with Concatenation of All Words - Leetcode | Java & C++ | Hard | Algorithm | DSAPrasun Personal · 9:33 · 1K views
The problem
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.
- For example, if
words = ["ab","cd","ef"], then"abcdef","abefcd","cdabef","cdefab","efabcd", and"efcdab"are all concatenated strings."acdbef"is not a concatenated string because it is not the concatenation of any permutation ofwords.
Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation:
The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words.
The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.
Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation:
There is no concatenated substring.
Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation:
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"].
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"].
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"].
Constraints:
1 <= s.length <= 1041 <= words.length <= 50001 <= words[i].length <= 30sandwords[i]consist of lowercase English letters.
Approach overview
Problem Overview: You get a string s and an array words. Every word has the same length. The task is to find all starting indices where a substring of s is formed by concatenating every word in words exactly once, in any order, with no extra characters.
Approach 1: Brute Force with Frequency Map (O(n * m * k) time, O(m) space)
Let n be the length of s, m the number of words, and k the length of each word. The total substring length to check is m * k. For every index i in s, extract the next m chunks of size k. Use a hash table to track the required word frequencies and compare them against the extracted words.
If any chunk does not exist in the map or exceeds the allowed count, stop early. If all chunks match exactly, record the index. This approach repeatedly rebuilds frequency maps for overlapping regions, which makes it inefficient when the string is large.
Approach 2: Sliding Window with Fixed Word Length (O(n) time, O(m) space)
The optimized solution treats the string as groups of words of length k. Build a frequency map of the target words. Then run multiple passes using a sliding window, starting from offsets 0 to k - 1. This ensures every window aligns with word boundaries.
Move the right pointer in steps of k, extracting one word at a time. Track counts in a second hash map. If the word exists in the target map, increase its count and expand the window. If a word appears too many times, move the left pointer forward by k and reduce counts until the window becomes valid again.
When the window size reaches exactly m words, you found a valid concatenation. Record the starting index and continue sliding. Each word enters and leaves the window at most once, giving near linear traversal of the string.
This method relies heavily on constant-time hash lookups and aligned substring extraction, making it the standard solution for problems involving fixed-length token matching in string processing.
Recommended for interviews: Interviewers expect the sliding window approach with a hash table. The brute force method demonstrates you understand the constraint that all words share equal length. The optimized sliding window shows stronger algorithmic thinking and efficient handling of repeated substring checks.
Approach 1: Sliding Window with Fixed Window Size
This approach uses a sliding window to find matching substrings. We utilize two hashmaps: one for the word list to track required counts of each word, and another to track what an occurring window currently constitutes.
The window slides over the string s while maintaining a fixed size (product of total words and word length). Each time the end of the window is extended, we evaluate if the slice of the string corresponds to a valid word by checking in the hashmap.
from collections import Counter
def findSubstring(s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
word_length = len(words[0])
word_count = len(words)
substring_length = word_length * word_count
word_map = Counter(words)
result = []
for i in range(len(s) - substring_length + 1):
seen_words = Counter()
for j in range(word_count):
word_start = i + j * word_length
word = s[word_start:word_start + word_length]
if word in word_map:
seen_words[word] += 1
if seen_words[word] > word_map[word]:
break
else:
break
if seen_words == word_map:
result.append(i)
return resultimport java.util.*;
public List<Integer> findSubstring(String s, String[] words) {
if (words.length == 0) return Collections.emptyList();
Map<String, Integer> wordCount = new HashMap<>();
for (String word : words) wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
int wordLength = words[0].length();
int subStringLength = wordLength * words.length;
List<Integer> indices = new ArrayList<>();
for (int i = 0; i <= s.length() - subStringLength; i++) {
Map<String, Integer> seen = new HashMap<>();
int j = 0;
while (j < words.length) {
int wordIndex = i + j * wordLength;
String sub = s.substring(wordIndex, wordIndex + wordLength);
if (!wordCount.containsKey(sub)) break;
seen.put(sub, seen.getOrDefault(sub, 0) + 1);
if (seen.get(sub) > wordCount.get(sub)) break;
j++;
}
if (j == words.length) indices.add(i);
}
return indices;
}#include <unordered_map>
#include <vector>
using namespace std;
vector<int> findSubstring(string s, vector<string>& words) {
if(words.empty()) return {};
unordered_map<string, int> wordMap;
unordered_map<string, int> windowMap;
int wordLen = words[0].size();
int wordCount = words.size();
int subLen = wordLen * wordCount;
vector<int> result;
for (auto &word : words) wordMap[word]++;
for (int i = 0; i <= s.size() - subLen; i++) {
windowMap.clear();
int j = 0;
for (; j < wordCount; j++) {
int wordBegin = i + j * wordLen;
string word = s.substr(wordBegin, wordLen);
if (wordMap.find(word) == wordMap.end()) break;
windowMap[word]++;
if (windowMap[word] > wordMap[word]) break;
}
if (j == wordCount) result.push_back(i);
}
return result;
}function findSubstring(s, words) {
if (!words || words.length === 0) return [];
let wordLength = words[0].length;
let wordCount = words.length;
let allWordsLength = wordLength * wordCount;
let result = [];
let wordMap = {};
// Fill wordMap
for (let word of words) {
wordMap[word] = (wordMap[word] || 0) + 1;
}
for (let i = 0; i <= s.length - allWordsLength; i++) {
let seenWords = {};
let j = 0;
for (; j < wordCount; j++) {
let wordStartIndex = i + j * wordLength;
let word = s.substring(wordStartIndex, wordStartIndex + wordLength);
if (!wordMap[word]) break;
seenWords[word] = (seenWords[word] || 0) + 1;
if (seenWords[word] > wordMap[word]) break;
}
if (j === wordCount) result.push(i);
}
return result;
}int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){
int wordLen = strlen(words[0]);
int allWordsLen = wordLen * wordsSize;
int strLen = strlen(s);
int *indices = (int *)malloc(sizeof(int) * strLen);
*returnSize = 0;
// Corner cases check
if (wordsSize == 0 || strLen < allWordsLen) return indices;
// Initialize word count
int wordCount[5000][26] = {0}; // assumption based index
int neededCount[26] = {0}, scar = 0;
for (int i = 0; i < wordsSize; i++) {
for (int j = 0; j < wordLen; j++) {
int wInd = words[i][j] - 'a';
if (wordCount[i][wInd] == 0) neededCount[wInd]++;
wordCount[i][wInd] = 1;
}
}
for (int i = 0; i <= strLen - allWordsLen; i++) {
int usedWords[26] = {0};
int j;
for (j = 0; j < allWordsLen; j += wordLen) {
int wIndex = s[i+j] - 'a';
if (++usedWords[wIndex] > neededCount[wIndex]) break;
}
if (j == allWordsLen) indices[(*returnSize)++] = i;
}
return indices;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> FindSubstring(string s, string[] words) {
if (words.Length == 0) return new List<int>();
Dictionary<string, int> wordCount = new Dictionary<string, int>();
foreach (string word in words) {
if (!wordCount.ContainsKey(word)) {
wordCount[word] = 0;
}
wordCount[word]++;
}
int wordLength = words[0].Length;
int subStringLength = wordLength * words.Length;
List<int> indices = new List<int>();
for (int i = 0; i <= s.Length - subStringLength; i++) {
Dictionary<string, int> seen = new Dictionary<string, int>();
int j = 0;
while (j < words.Length) {
int wordIndex = i + j * wordLength;
string sub = s.Substring(wordIndex, wordLength);
if (!wordCount.ContainsKey(sub)) break;
if (!seen.ContainsKey(sub)) seen[sub] = 0;
seen[sub]++;
if (seen[sub] > wordCount[sub]) break;
j++;
}
if (j == words.Length) indices.Add(i);
}
return indices;
}
}Using Python's Counter from collections, this script creates a dictionary for word counts and matches it against each possible starting location by traversing employing a nested for-loop structure with controlled breaks.
Time complexity: O(n * m) where n is the string length and m is the number of words. Utilization of Counters is efficient.
Space complexity: O(k), where k counts for required map storage.
Approach 2: Hash Table + Sliding Window
We use a hash table cnt to count the number of times each word appears in words, and use a hash table cnt1 to count the number of times each word appears in the current sliding window. We denote the length of the string s as m, the number of words in the string array words as n, and the length of each word as k.
We can enumerate the starting point i of the sliding window, where 0 \lt i < k. For each starting point, we maintain a sliding window with the left boundary as l, the right boundary as r, and the number of words in the sliding window as t. Additionally, we use a hash table cnt1 to count the number of times each word appears in the sliding window.
Each time, we extract the string s[r:r+k]. If s[r:r+k] is not in the hash table cnt, it means that the words in the current sliding window are not valid. We update the left boundary l to r, clear the hash table cnt1, and reset the word count t to 0. If s[r:r+k] is in the hash table cnt, it means that the words in the current sliding window are valid. We increase the word count t by 1, and increase the count of s[r:r+k] in the hash table cnt1 by 1. If cnt1[s[r:r+k]] is greater than cnt[s[r:r+k]], it means that s[r:r+k] appears too many times in the current sliding window. We need to move the left boundary l to the right until cnt1[s[r:r+k]] = cnt[s[r:r+k]]. If t = n, it means that the words in the current sliding window are exactly valid, and we add the left boundary l to the answer array.
The time complexity is O(m times k), and the space complexity is O(n times k). Here, m and n are the lengths of the string s and the string array words respectively, and k is the length of the words in the string array words.
function findSubstring(s: string, words: string[]): number[] {
const cnt: Map<string, number> = new Map();
for (const w of words) {
cnt.set(w, (cnt.get(w) || 0) + 1);
}
const ans: number[] = [];
const [m, n, k] = [s.length, words.length, words[0].length];
for (let i = 0; i < k; i++) {
let [l, r] = [i, i];
const cnt1: Map<string, number> = new Map();
while (r + k <= m) {
const t = s.substring(r, r + k);
r += k;
if (!cnt.has(t)) {
cnt1.clear();
l = r;
continue;
}
cnt1.set(t, (cnt1.get(t) || 0) + 1);
while (cnt1.get(t)! > cnt.get(t)!) {
const w = s.substring(l, l + k);
cnt1.set(w, cnt1.get(w)! - 1);
if (cnt1.get(w) === 0) {
cnt1.delete(w);
}
l += k;
}
if (r - l === n * k) {
ans.push(l);
}
}
}
return ans;
}func findSubstring(s string, words []string) (ans []int) {
cnt := make(map[string]int)
for _, w := range words {
cnt[w]++
}
m, n, k := len(s), len(words), len(words[0])
for i := 0; i < k; i++ {
l, r := i, i
cnt1 := make(map[string]int)
for r+k <= m {
t := s[r : r+k]
r += k
if _, exists := cnt[t]; !exists {
cnt1 = make(map[string]int)
l = r
continue
}
cnt1[t]++
for cnt1[t] > cnt[t] {
w := s[l : l+k]
cnt1[w]--
if cnt1[w] == 0 {
delete(cnt1, w)
}
l += k
}
if r-l == n*k {
ans = append(ans, l)
}
}
}
return
}class Solution {
/**
* @param String $s
* @param String[] $words
* @return Integer[]
*/
function findSubstring($s, $words) {
$cnt = [];
foreach ($words as $w) {
if (isset($cnt[$w])) {
$cnt[$w]++;
} else {
$cnt[$w] = 1;
}
}
$ans = [];
$m = strlen($s);
$n = count($words);
$k = strlen($words[0]);
for ($i = 0; $i < $k; $i++) {
$l = $i;
$r = $i;
$cnt1 = [];
while ($r + $k <= $m) {
$t = substr($s, $r, $k);
$r += $k;
if (!isset($cnt[$t])) {
$cnt1 = [];
$l = $r;
continue;
}
if (isset($cnt1[$t])) {
$cnt1[$t]++;
} else {
$cnt1[$t] = 1;
}
while ($cnt1[$t] > $cnt[$t]) {
$w = substr($s, $l, $k);
$cnt1[$w]--;
if ($cnt1[$w] == 0) {
unset($cnt1[$w]);
}
$l += $k;
}
if ($r - $l == $n * $k) {
$ans[] = $l;
}
}
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Fixed Window Size | Time complexity: O(n * m) where n is the string length and m is the number of words. Utilization of Counters is efficient. Space complexity: O(k), where k counts for required map storage. |
| Hash Table + Sliding Window | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Frequency Map | O(n * m * k) | O(m) | Good for understanding the problem constraints and verifying correctness on small inputs |
| Sliding Window with Fixed Word Size | O(n) | O(m) | Best general solution when all words share equal length and fast substring scanning is needed |
Frequently asked questions
Is Substring with Concatenation of All Words easy or hard?
Substring with Concatenation of All Words is categorized as a Hard problem because it combines multiple techniques: sliding window alignment, hash map frequency tracking, and careful handling of overlapping substrings. The tricky part is managing multiple window offsets and preventing redundant substring checks.
Substring with Concatenation of All Words Python/Java solution
Most implementations use a sliding window with hash maps. Python solutions typically rely on dictionaries and substring slicing, while Java solutions use HashMap and substring operations. Both follow the same idea: scan the string in word-length steps, maintain frequency counts, and shrink the window when limits are exceeded.
How to solve Substring with Concatenation of All Words in O(n)?
Build a hash map containing the required frequency of each word. Run k sliding window passes where k is the word length, ensuring each window aligns with word boundaries. Expand the window by one word at a time, adjust counts when frequencies exceed limits, and record indices when the window contains exactly m valid words.
What is the best approach for Substring with Concatenation of All Words?
The most efficient approach uses a sliding window combined with a hash table. Because all words have equal length, the algorithm scans the string in steps of that length and tracks word frequencies inside the window. This reduces redundant checks and achieves near O(n) traversal of the string.
Is Substring with Concatenation of All Words asked at Google/Amazon/Meta?
Substring with Concatenation of All Words appears in interview preparation lists for companies like Amazon, Google, and Meta because it tests sliding window logic, hash map usage, and careful string indexing. The problem evaluates how well candidates optimize repeated substring checks.
What data structure is used in Substring with Concatenation of All Words?
The core data structure is a hash table that stores the frequency of each word in the input list. Another hash map tracks counts of words currently inside the sliding window. Two pointers maintain the window boundaries while scanning the string.
What is the time complexity of Substring with Concatenation of All Words?
The optimal sliding window solution runs in O(n) time relative to the length of the string, with additional factors based on word length for substring extraction. Each word-sized segment enters and leaves the window at most once. Space complexity is O(m) for storing the frequency map of the words.