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) in s that is a concatenation of each word in words exactly 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).

Analysis

• Take care of empty s or words
• Store words in a map, key is words, value is the count of words。比如 "foo, 1", "bar, 1"
• Get length of word in words: len
• Scan s from beginning: for(i=0; i+len smaller than length of s ;i++)
  • Make a copy of map
  • Loop: get the jth word str starting from i (j from 0 to ?)
    • if (no str is found in map): break loop, start a new i
    • else:
      • check the value of words in map
        • if value==1, remove this word from copied map
        • if value>1, update value-1
    • Check if copied map is empty
      • Yes: add i to result, break from current loop of j
      • No: do nothing, continue with loop
• Return result

Code

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;
    int len = words[0].length();
    if (words.length*len>s.length()) return res; //case when total length of words is longer than s

    Map<String, Integer> map = new HashMap<String, Integer>();
    for (int i=0; i<words.length; i++){
        if (map.containsKey(words[i])){map.put(words[i], (map.get(words[i])+1));}
        else {map.put(words[i],1);}
    }

    for(int i=0; i+words.length*len < s.length()+1;i++){
        Map<String, Integer> copyMap = new HashMap<String, Integer>(map);
        for (int j=0; j<words.length; j++){
            String str = s.substring(i+j*len, i+j*len+len);
            if (!copyMap.containsKey(str)) {break;}
            else {
                if (copyMap.get(str)==1) {copyMap.remove(str);}
                else {copyMap.put(str, (copyMap.get(str)-1));}
            }
            if (copyMap.isEmpty()) {res.add(i);}
        }
    }
    return res;
}

Reference

Leetcode