30. Substring with Concatenation of All Words

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

For example, given: s:"barfoothefoobarman" words:["foo", "bar"]

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

Code1 : Two Maps (one for record, the other for scanning)

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> indices;
        if (s.size() == 0 or words.size() == 0) return indices; 
        unordered_map<string, int> counts;
        for (string word : words)
            counts[word]++;

        int n = s.size(), num = words.size(), len = words[0].length();
        for (int i = 0; i <= n - num * len; i++) {
            unordered_map<string, int> seen;
            int j = 0;
            for (; j < num; j++) {
                string word = s.substr(i + j * len, len);
                if (counts.find(word) != counts.end()) {
                    seen[word]++;
                    if (seen[word] > counts[word]) // overuse
                        break;
                } 
                else break; // did not find
            }
            if (j == num) indices.push_back(i);
        }
        return indices;
    }
};

Code2 (Java) by harrychaoyanghe

public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> res = new LinkedList<>();
        if (L.length == 0 || S.length() < L.length * L[0].length())   return res;
        int N = S.length();
        int M = L.length; // *** length
        int wl = L[0].length();
        Map<String, Integer> map = new HashMap<>(), curMap = new HashMap<>();
        for (String s : L) {
            map.put(s, map.getOrDefault(s,0) + 1);

        }
        String str = null, tmp = null;
        for (int i = 0; i < wl; i++) {
            int count = 0;  // remark: reset count 
            int start = i;
            for (int r = i; r + wl <= N; r += wl) {
                str = S.substring(r, r + wl);
                if (map.containsKey(str)) {
                      curMap.put(str, curMap.getOrDefault(str, 0) + 1);                   
                    if (curMap.get(str) <= map.get(str))    count++;

                    while (curMap.get(str) > map.get(str)) {
                        tmp = S.substring(start, start + wl);
                        curMap.put(tmp, curMap.get(tmp) - 1);
                        start += wl;

                        //the same as https://leetcode.com/problems/longest-substring-without-repeating-characters/
                        if (curMap.get(tmp) < map.get(tmp)) count--;

                    }
                    if (count == M) {
                        res.add(start);
                        tmp = S.substring(start, start + wl);
                        curMap.put(tmp, curMap.get(tmp) - 1);
                        start += wl;
                        count--;
                    }
                }else {
                    curMap.clear();
                    count = 0;
                    start = r + wl;//not contain, so move the start
                }
            }
            curMap.clear();
        }
        return res;
    }
}

My C++ Implementation based on Code 2:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> answer;
        int n = s.length(),  num = words.size(), len = words[0].length();
        if(num == 0 || n < len) return answer;
        unordered_map <string, int> rec, curRec;

        for(string word : words)++rec[word];  

        string rightStr, leftStr;
        for(int i = 0; i < len; i ++){
            int count = 0;
            int left = i;
            for(int right = i; right+ len <= n ; right+= len){
                rightStr = s.substr(right, len);
                if(rec.find(rightStr)!= rec.end()){
                    if(++curRec[rightStr] <= rec[rightStr]) count++;
                    while(curRec[rightStr] > rec[rightStr]){ // we have contained more elements than we need, so use left to adjust

                        leftStr = s.substr(left, len);
                        if(--curRec[leftStr] < rec[leftStr]) count--;
                        left+= len;

                    }
                    if(count == num){  // we find the answer
                        answer.push_back(left);

                        leftStr = s.substr(left,len);   // we need to explicity again since there is a case that do not go 
                                                        // into the while loop/initialize leftStr
                        --curRec[leftStr];
                        count--;                        // we need to substract 1 since one essential element is lost as we progreess
                                                        // to search to the right after finding the right solution
                                                        // in the current position;
                        left+= len;
                    }                    
                }else{
                    curRec.clear();
                    count = 0;                 
                    left = right + len;
                }
            }
                curRec.clear();
        }

        return answer;
    }
};