Substring with Concatenation of All Words

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

滑动窗口的神题。思路和 Minimum Window Substring 非常相似。

但是这个题tricky一点在于要发现，只要遍历 string  每个单词长度（K） 遍 就可以包含全部情况。

几个容易出错的地方在代码中有标注。

这题是要求 without intervening characters的。这里跟  Minimum Window Substring 要求不同。所以就导致了再一次遍历中存在着重新初始化的情况（map初始化）

这一点应该是可以提升的，毕竟每次遇见intervening string就重启一个大的map很耗时。如果可以只修复map被污染的部分会好些。

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
 
        if (words.length == 0){
            
            return res;
        }
        
        int wl = words[0].length();
        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 size = words.length;
        for(int start=0; start<wl; start++){
            HashMap<String, Integer> map = new HashMap<String, Integer>(MAP);
            int cnt = 0;
            int l = start;
            //i<= s.length() - wl   Notice the equal sign, alway try out examples to ensure it.
            for(int i=start; i<=s.length()-wl; i+=wl){
                String word = s.substring(i,i+wl);
                if(l > s.length() - wl*size)
                    break;
                if(map.containsKey(word)){
                    if( map.get(word) > 0){
                        map.put(word, map.get(word)-1);
                        cnt += 1;
                    }else if(map.get(word) == 0){
                        while(l<i && map.get(word) == 0){
                            String leftWord = s.substring(l,l+wl);
                            map.put(leftWord, map.get(leftWord)+1);
                            cnt -= 1;
                            l += wl;
                        }
                        i -= wl;
                    }
                }else{
                    l = i+wl;
                    cnt = 0;
                    map = new HashMap<String, Integer>(MAP);
                }
                //Notice: check cnt at the end instead of front. Otherwise can't check the instance happened at very end
                if(cnt == size){
                    res.add(l);
                }
            }
        }
        return res;
    }