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. Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Key Insights

• Each word in the words array has the same length, making it easier to determine the length of the concatenated substring.
• The total length of the concatenated substring is the length of one word multiplied by the number of words.
• A sliding window approach can be used to efficiently check substrings of s against the word list.
• A hash table (or dictionary) will store the frequency of each word to facilitate quick lookups and comparisons.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of the string s and m is the total length of all words combined (length of each word multiplied by the number of words).
Space Complexity: O(m), where m is the number of unique words in the words array, due to the hash table storing the frequency of each word.

Solution

To solve the problem, we can use the following approach:

1. Calculate the length of each word and the total length of the concatenated substring.
2. Create a frequency map (hash table) for the words in the words array.
3. Use a sliding window of the total length of the concatenated substring over the string s.
4. For each position in s, check if the substring matches the concatenated words by comparing the frequency of the words in the current window with the frequency map.
5. If they match, record the starting index.

Code Solutions