30. Substring with Concatenation of All Words

This problem is similar to 3. Longest Substring Without Repeating Characters. As mentioned in the title, we can use slide window and hashmap to solve the problem. The key though is sliding by a word instead of a character.

The slide window includes three parameters:

1. begin denotes the begin index of current window
2. current denotes the frequency of words contained in the current window
3. size denotes the number of words contained in current window

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> resultList = new ArrayList<Integer>();
    if( s == null || s.length() < 1 || words.length < 1)
        return resultList;
		
    Map<String, Integer> wordToFreq = new HashMap<String, Integer>();
    for(int i = 0; i < words.length; i++) {
        wordToFreq.put(words[i], wordToFreq.getOrDefault(words[i], 0) + 1);
    }
	
    int length = words[0].length();
    String str[] = new String[s.length()];
    for(int i = 0; i < length; i++) { 
		// initialize slide window
        int begin = i;
        Map<String, Integer> current = new HashMap<String, Integer>();
        int size = 0;	
		
        for(int j = i; j <= s.length() - length; j += length) { // slide by the length of word
            str[j] = s.substring(j, j + length);
            if( wordToFreq.containsKey(str[j]) ) { // update slide window
                begin = begin == -1 ? j : begin;
                current.put(str[j], current.getOrDefault(str[j], 0) + 1);
                size++;
                if( size == words.length ) {
                    if( current.equals(wordToFreq) )
                        resultList.add(begin);
                    current.put(str[begin], current.get(str[begin]) - 1);
                    size--;
                    begin += length;
                }
            } else { // reset the slide window
                begin = -1;
                current.clear();
                size = 0;
            }
        }
    }
    return resultList;
}