Substring with Concatenation of All Words
Problem Description
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 <= 104
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30
sandwords[i]consist of lowercase English letters.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest approach is to generate all possible substrings of the given string s that can be formed with the total length of all the words. For each substring, check if the substring is a valid concatenation of the words in the given word list with the help of permutations. If it is, record the starting index.
Steps:
- Calculate the total length of all words combined:
substring_length = words.length * word_length. - Iterate over each substring of
swith lengthsubstring_length. - For each substring, generate all permutations of the word list.
- Check if any permutation matches the substring.
- If a match is found, store the starting index of the substring.
Code:
- Time Complexity:
O((n - totalLength + 1) * m!), wherenis the length ofsandmis the number of words. Generating all permutations takesO(m!). - Space Complexity:
O(m!)to store permutations.
2. Sliding Window with HashMap
Intuition:
Instead of generating permutations, we can use a sliding window with the help of a hashmap to keep track of the word count. This allows us to efficiently check if the current sliding window contains a valid concatenation of the words.
Steps:
- Create a hashmap
wordCountcontaining the frequency of each word. - Iterate over
sin a sliding window where the step is the word length. - For each starting position, initialize a new hashmap
seenWordsto count words in the current window. - Slide over the segment, counting words, and if the window is invalid (i.e., a word is missing, or we have too many of a word), reset and start from the next word boundary.
- If the window is valid (i.e., all word counts match), add the starting index to the result.
Code:
- Time Complexity:
O(n * word_length), wherenis the length ofs. The map operations areO(1), and we slide oversword by word. - Space Complexity:
O(m), wheremis the number of distinct words.