Substring with Concatenation of All Words.cpp

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if(words.empty())return {};
        int len = s.size(), step = words[0].size(), count = words.size();
        unordered_map<string, int> map;
        vector<int> res;
        for(auto word : words)++map[word];
        for(int i = 0; i < step; ++i)
        {
            int left = i, currCount = 0;
            unordered_map<string, int> currMap;
            for(int j = i; j < len; j += step)
            {
                string str = s.substr(j, step);
                if(map.find(str) != map.end())
                {
                    ++currCount;
                    ++currMap[str];
                    if(currMap[str] > map[str])
                    {
                        while(true)
                        {
                            string del = s.substr(left, step);
                            --currCount;
                            left += step;
                            --currMap[del];
                            if(!currMap[del])currMap.erase(del);
                            if(del == str)break;
                        }
                    }
                    if(currCount == count)res.push_back(left);
                }
                else
                {
                    left = j + step;
                    currMap.clear();
                    currCount = 0;
                }
            }
        }
        return res;
    }
};