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.
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 of words.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 <= 30s and words[i] consist of lowercase English letters.The key challenge in #30 Substring with Concatenation of All Words is to find all starting indices where a substring is formed by concatenating every word in the given list exactly once and without gaps. Since all words have the same length, this property enables an efficient sliding window strategy.
A common approach uses a hash table to store the required frequency of each word. Iterate through the string with multiple starting offsets (from 0 to wordLength - 1). For each offset, move a sliding window in steps of wordLength, extracting substrings and checking them against the frequency map. Maintain another hash map for the current window and adjust the window when a word appears more times than expected.
This technique avoids checking every possible permutation and significantly reduces redundant work. With careful window adjustments and hash lookups, the method efficiently scans the string while ensuring the concatenation constraint is satisfied.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Hash Map | O(n * k) | O(k) |
Techdose
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.
Time complexity: O(n * m * k) where n is the length of the string, m is the length of each word, and k is the number of words.
Space complexity: O(m) for the dictionaries holding word counts.
1int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){
2 int wordLen = strlen(words
The C code uses arrays to count the appearance of each letter in words, and then evaluates at each position if a segment of the string matches a permutation of the words.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
All words have the same length, so valid concatenations must align with word boundaries. By starting the sliding window at offsets from 0 to wordLength - 1, we ensure every possible alignment in the string is examined efficiently.
Yes, this is a well-known hard-level string and sliding window problem frequently discussed in coding interview preparation. Variations of substring matching with hash maps and window techniques often appear in FAANG-style interviews.
A hash table (or hash map) is the most useful data structure for this problem. It stores the expected frequency of each word and allows constant-time checks when validating words encountered in the sliding window.
The optimal approach uses a sliding window combined with a hash map to track the frequency of required words. By scanning the string in steps of the word length and maintaining counts of words inside the window, we can efficiently detect valid concatenations without generating permutations.