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

Analysis

Use fixed length sliding window. The length is the length of all strings in words (words.length * words[0].length()); Within the sliding window, find out if it contains all the strings of words.

My Solution

    public List<Integer> findSubstring(String s, String[] words) {
        int len = words.length * words[0].length();
        List<Integer> result = new ArrayList<>();
        int k = words[0].length();
        HashMap<String, Integer> map = new HashMap<>();
        for (String st : words) {
            map.put(st, map.getOrDefault(st, 0) + 1);
        }
        for (int i=0; i+len <= s.length(); ++i) {
            HashMap<String, Integer> count = new HashMap<>();
            int c = 0;
            for (int j=i; j<i+len; j+=k) {
                String word = s.substring(j, j+k);
                count.put(word, count.getOrDefault(word, 0) + 1);
                if (!map.containsKey(word) || count.get(word) > map.get(word)) {
                    break;
                }
                c += k;
            }
            if (c == len) {
                result.add(i);
            }
        }
        return result;
    }

Another solution

https://discuss.leetcode.com/topic/54662/92-java-o-n-with-explaination

Do not understand the logic. What does the outer loop mean?

Work on it later!