Substring With Concatenation Of All Words - Leetcode Solution

Problem Description: You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

Example 1: Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting from index 0 and 9 are "barfoo" and "foobar" respectively, both concatenated strings are a concatenation of "foo" and "bar" in any order.

Example 2: Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: [] Explanation: There are no possible concatenations of words in s.

Approach:

1. Count frequency of all words in the given array.
2. Traverse through length of string s with step size equal to length of each word.
3. For each index, check if there is a concatenation of all words and return the index.
4. For checking if there is a concatenation of all words, use a map to count the frequency of all words in the current substring and compare it with the frequency of words in the array of words.

Detailed Solution:

1. We start by creating a map of word frequencies for all the words in the words array.

for(auto word : words){ freqs[word]++; }

2. Create a map to count the word frequencies of substring of same length as words array.

unordered_map <string,int> words_temp;

3. Traverse through length of string s with step size equal to length of each word.

for(int i = 0; i < L; i++){ int j = i + M - 1; int k = i;

words_temp.clear();

while(j < N){

    string word = s.substr(k,M);
    words_temp[word]++;

    while(words_temp[word] > freqs[word]){
        words_temp[s.substr(k,M)]--;
        k+= M;
    }

    if(j - k + 1 == M*W){
        res.push_back(k);
    }

    j+= M;
}

}

4. For each substring of the same length as the words array, we store the frequency of each word in a map and compare it with the frequency of words in the array of words. If it matches, we add the starting index of the substring to the result vector.

string word = s.substr(k,M); words_temp[word]++;

while(words_temp[word] > freqs[word]){ words_temp[s.substr(k,M)]--; k+= M; }

if(j - k + 1 == M*W){ res.push_back(k); }

5. Since the length of all the words in the array is same, we use M as the length of each word and W as the total number of words in the array.

The complete solution is given below.

1