Leetcode Study Day 15

Substring with Concatenation of All Words

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s is a substring that 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 substring because it is not the concatenation of any permutation of words.
Return 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: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6.
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.
The output order does not matter. Returning [9,0] is fine too.
Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16.
There is no substring of length 16 in s that is equal to the concatenation of any permutation of words.
We return an empty array.
Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9.
The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words.
The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words.
The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.

Solution

The solution is firstly, we store the word in the array words in a unordered_map. For each word, we count the number of times it appears. Then we use the sliding window method to find the substring. We use a method checkSubstring to check if the substring of the original input string s is a concatenated substring.

vector<int> findSubstring(string s, vector<string>& words) {
        vector <int> answer;
        int singleWordLen = words[0].size();
        int windowSize = words.size() * singleWordLen;
        // creating a map stores words count
        unordered_map <string, int> wordCount;
        for (int i = 0; i < words.size(); i++){
            wordCount[words[i]]++;
        }
        int i = 0;
        while (i + windowSize <= s.size()){
            if (checkSubstring(wordCount, s.substr(i, windowSize), singleWordLen))
                answer.push_back(i);
            i++;
        }
        return answer;
    }

In the function checkSubstring, we iterate the substring, which is passed in the main function and check if the word in the array words is in the substring. If it is, we decrease the count of the word in the map. If the count is equal to -1, which means the word appears more times than it should be, we return false. If the word is not in the map, we return false. If the word is in the map and the count is not equal to -1, we continue to check the next word. If we finish checking all the words in the map, we return true.

It is noticeable that wordCount is passed by value, any changes made to it within the checkSubstring function are local to that function and do not affect the original wordCount map in the findSubstring method. This means that every time checkSubstring is called, it receives a fresh copy of the wordCount map with the original word counts. As a result, there’s no need to reset the map after each call to checkSubstring.

bool checkSubstring(unordered_map <string, int> wordCount, string s, int singleWordLen){
    for (int i = 0; i < s.size(); i += singleWordLen){
        string subString = s.substr(i, singleWordLen);
        if (wordCount.find(subString) != wordCount.end()){
            if (--wordCount[subString] == -1)
                return false;
        }
        else
            return false;
    }
    return true;
}

Full code

class Solution {
public:
    bool checkSubstring(unordered_map <string, int> wordCount, string s, int singleWordLen){
        for (int i = 0; i < s.size(); i += singleWordLen){
            string subString = s.substr(i, singleWordLen);
            if (wordCount.find(subString) != wordCount.end()){
                if (--wordCount[subString] == -1)
                    return false;
            }
            else
                return false;
        }
        return true;
    }

    vector<int> findSubstring(string s, vector<string>& words) {
        vector <int> answer;
        int singleWordLen = words[0].size();
        int windowSize = words.size() * singleWordLen;
        // creating a map stores words count
        unordered_map <string, int> wordCount;
        for (int i = 0; i < words.size(); i++){
            wordCount[words[i]]++;
        }
        int i = 0;
        while (i + windowSize <= s.size()){
            if (checkSubstring(wordCount, s.substr(i, windowSize), singleWordLen))
                answer.push_back(i);
            i++;
        }
        return answer;
    }
};