https://leetcode.com/problems/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).

暴力解法就是所有substring with length word_count * word_length to see if we contains all words

loop from 0 to string_length - word_count * word_length (n - m * len)

time: (n - m * len) * m // for each substring checking m words exactly once

剪枝：假如 str = w1w2m1w3w1w2，words[w1,w2,w3]. 当我们知道m1不在words里的时候，我们就没必要再check w2m1w3 和 m1w3w1，即包含m1的所有substring。

这样就可以类似想到 Minimum Window Substring，用sliding window

因为对于s中的每个字母，它可以是word的任何部分，这样我们需要利用 words are same length，即所有的case 包含在以 0 to (word_length - 1) 开始的string 中，每次的增量是word的长度，也就是说 固定每个字母在组成word中的位置

或者是说，把这个string 按照word长度来划分可得到word的全部分法

其实只用把word 假设是长度为1 基本就是和 Minimum Window Substring，唯一不同就是不能有其他字母在其中

        int m = words[0].length();
        int n = s.length();

        HashMap<String, Integer> dict = new HashMap<String, Integer>();
        for (String word : words) {
            if (!dict.containsKey(word)) {
                dict.put(word, 1);
            } else {
                dict.put(word, dict.get(word) + 1);
            }
        }
        // traverse string m times
        for (int i = 0; i < m; ++i) {
            // Start index of current substring
            int start = i;
            // count of words in dict
            int count = 0;
            HashMap<String, Integer> has = new HashMap<String, Integer>();
            for (int r = i; r <= n - m; r += m) {
                String word = s.substring(r, r+m);
                if (dict.containsKey(word)) {
                    if (has.get(word) == null) has.put(word, 0);
                    has.put(word, has.get(word) + 1);
                    count++;
                    // its too much for us have this word, discard word from left
                    while (dict.get(word) < has.get(word)) {
                        String discard = s.substring(start, start + m);
                        start = start + m;
                        has.put(discard, has.get(discard) - 1);
                        count--;
                    }

                    if (count == words.length) {
                        result.add(start);
                    }

                } else {
                    // no need to check all substring contain current word
                    // start from next index
                    start = r + m;
                    has.clear();
                    count = 0;
                }
            }
        }