Watch 10 video solutions for Substring with Concatenation of All Words, a hard level problem involving Hash Table, String, Sliding Window. This walkthrough by Techdose has 40,837 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |