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: 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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| Sliding Window with Fixed Window Size | 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. |
| Hash Table + Sliding Window | — |
| 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 |
Substring with Concatenation of All Words | Leetcode #30 • Techdose • 40,837 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 FleetCode