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.Problem Overview: Given a string s and a list of words where every word has the same length, find all starting indices where the substring is formed by concatenating every word exactly once without extra characters. The order of words can vary, but the substring length must equal words.length * wordLength.
Approach 1: Brute Force with Hash Map Check (O(n * k * w) time, O(k) space)
The straightforward idea is to check every possible starting index in s. From each index, extract a substring of total length k * w where k is the number of words and w is the word length. Split the substring into chunks of size w and track frequencies using a hash map. Compare this frequency map with the required word frequency map. If they match, record the starting index. This approach is easy to implement and demonstrates the core observation that words are fixed length, but repeated substring extraction and map comparisons make it slow for large inputs.
Approach 2: Sliding Window with Fixed Word Length (O(n * w) time, O(k) space)
The optimized solution leverages the fact that all words share the same length. Instead of checking every character index independently, iterate over w possible starting offsets and process the string in word-sized steps. Maintain a sliding window and track word frequencies using a hash table. As you scan the string in increments of w, extract each word and update counts. If a word appears too many times, shrink the window from the left until the frequency constraint is restored. When the window size reaches exactly k words, record the starting index. This avoids rebuilding maps repeatedly and processes each word chunk only once.
This technique combines sliding window mechanics with constant-length token parsing from the string. The key insight: treat the string as a sequence of fixed-size words instead of individual characters. That drastically reduces redundant work.
Recommended for interviews: The sliding window approach is the expected solution. Interviewers want to see recognition of the fixed word length constraint and the ability to convert a character problem into a word-indexed window. Starting with the brute force method shows understanding of the problem structure, but implementing the optimized sliding window demonstrates strong algorithmic thinking and practical use of hash maps.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Hash Map Validation | O(n * k * w) | O(k) | Good for understanding the problem or when input sizes are small |
| Sliding Window with Fixed Word Length | O(n * w) | O(k) | Optimal solution for interviews and large inputs |
Substring with Concatenation of All Words | Leetcode #30 • Techdose • 22,728 views views
Watch 9 more video solutions →Practice Substring with Concatenation of All Words with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor