LeetCode - 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).


public class Solution {
      public ArrayList<Integer> findSubstring(String S, String[] L) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(L==null || L.length==0) return null;
        int n = L.length, m = L[0].length(), l=S.length();
        ArrayList<Integer> res = new ArrayList<Integer>();
     
        Map<String,Integer> covered = new HashMap<String,Integer>();
        for(int j=0;j<n;j++){
            if(covered.containsKey(L[j])){
                covered.put(L[j],covered.get(L[j])+1);
            }else{
                covered.put(L[j], 1);
            }
        }
     
        int i=0;
        while(l-i>=n*m){
            Map<String, Integer> temp = new HashMap<String, Integer>(covered);
            for(int j=0;j<n;j++){
                String testStr = S.substring(i+j*m,i+(j+1)*m);
                if(temp.containsKey(testStr)){
                    if(temp.get(testStr)-1==0)
                        temp.remove(testStr);
                    else
                        temp.put(testStr,temp.get(testStr)-1);
                }else
                    break;
            }
            if(temp.size()==0) res.add(i);
            i++;
        }
        return res;  
    }
}

==============

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return res;
        }
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (String word : words) {
            if (map.containsKey(word)) {
                map.put(word, map.get(word) + 1);
            } else {
                map.put(word, 1);
            }
        }
        int n = words.length;
        int len = words[0].length();
     
        for (int i = 0; i <= s.length() - n * len; i++) {
            HashMap<String, Integer> tmpMap = new HashMap<String, Integer>(map);
            int j = i;
            boolean qualified = true;
            while (tmpMap.size() != 0) {
                String nextSub = s.substring(j, j + len);
                Integer val = tmpMap.get(nextSub);
                if (val != null) {
                    if (val == 1) {
                        tmpMap.remove(nextSub);
                    } else {
                        tmpMap.put(nextSub, val - 1);
                    }
                    j += len;
                } else {
                    qualified = false;
                    break;
                }
            }
            if (qualified) res.add(i);
        }
        return res;
    }
}

========

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return res;
        }
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (String word : words) {
            if (map.containsKey(word)) {
                map.put(word, map.get(word) + 1);
            } else {
                map.put(word, 1);
            }
        }
        int len = words[0].length();
        for (int i = 0; i < len; i++) {
            HashMap<String, Integer> copy = new HashMap<>();
            int left = i;
            int right = i;
            while (true) {
                if (right - left != words.length * len) {
                    if (left + words.length * len > s.length()) break;
                    right += len;
                    if (right > s.length()) break;
                    String word = s.substring(right - len, right);
                    if (!map.containsKey(word)) {
                        copy.clear();
                        left = right;
                    } else {
                        while (copy.get(word) == map.get(word)) {
                            String word2 = s.substring(left, left + len);
                            copy.put(word2, copy.get(word2) - 1);
                            left += len;
                        }
                        if (!copy.containsKey(word)) {
                            copy.put(word, 1);
                        } else {
                            copy.put(word, copy.get(word) + 1);
                        }
                    }
                }
                if (words.length * len == right - left) {
                    res.add(left);
                    left += len;
                    String word = s.substring(left - len, left);
                    copy.put(word, copy.get(word) - 1);
                }
            }
        }
        return res;
    }
}