Substring with Concatenation of All Words

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

class Solution {//passed only the small test
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> r;
      //  if (S.empty() || L.empty() || L[0].empty()) return r;
        int const word_length = L[0].size();
        int const window_length = word_length * L.size();
        for(int start = 0; start + window_length <= S.length(); ++start){
            string str(S.substr(start, window_length));
            vector<string> v(L);


            bool flag = true;
            for(int ii = 0; ii < L.size(); ++ii){
                vector<string>::iterator it = find(v.begin(),v.end(), str.substr(ii*word_length, word_length));
                if (it == v.end()){
                    flag = false;
                    break;
                }else{
                    v.erase(it);
                }
            }//for ii
            if (flag){
                r.push_back(start);
            }




        }//for start
        return r;
    }
}; 

 class Solution {//passed large test //hash on the string units
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> r;
      //  if (S.empty() || L.empty() || L[0].empty()) return r;
        int const word_length = L[0].size();
        int const window_length = word_length * L.size();
        unordered_map<string, int> lmap;
        for(int ii = 0; ii < L.size(); ++ii){
            ++lmap[L[ii]];
        }
        for(int start = 0; start + window_length <= S.length(); ++start){
            unordered_map<string, int> check_map(lmap);

            bool flag = true;
            for(int ii = 0; ii * word_length < window_length; ++ii){                
                if ((--check_map[S.substr(start+ii*word_length, word_length)]) < 0){
                    flag = false;
                    break;
                }
            }//for ii
            if (flag){
                r.push_back(start);
            }




        }//for start
        return r;
    }
};