Substring with Concatenation of All Words

The key to this problem is that we can split the string s into groups. Let's say the length of word in word dictionary is l, then we can first find start index with the string splited at 0, l, 2 * l, 3 * l, .... Then we move all these indexes one step forward and try to find start index with words start at 1, l + 1, 2 * l + 1, 3 * l + 1, .... We keep moving these indexes until we meet l - 1, 2 * l - 1, 3 * l - 1, 4 * l - 1, ....

For each of these groups, we can apply sliding window method. Let a and b be two index, we always keeps the words between a and b are in the dictionary and add a to result if substring between a and b is a concatenations of all words. As we will visit every index in the string once so even we have two loops in the program, the time complexity will be $O(N)$.

public class SubstringWithConcatenationOfAllWords {
    public List<Integer> findSubstring(String s, String[] words) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (words.length == 0) return result;

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

        if (l == 0) return result;
        if (s.length() < l * n) return result;

        HashMap<String, Integer> wordsCount = new HashMap<String, Integer>();

        for (String w : words) {
            if (wordsCount.containsKey(w)) {
                wordsCount.put(w, wordsCount.get(w) + 1);
            } else {
                wordsCount.put(w, 1);
            }
        }

        String[] splited = new String[s.length() - l + 1];

        for (int i = 0; i < splited.length; i++) {
            splited[i] = s.substring(i, i + l);
        }

        for (int i = 0; i < l; i++) {
            int count = 0;
            int a = i;
            HashMap<String, Integer> partCount = new HashMap<String, Integer>();

            for (int b = i; b < splited.length; b += l) {
                String word = splited[b];

                if (!wordsCount.containsKey(word)) {
                    a = b + l;
                    partCount.clear();
                    count = 0;
                    continue;
                }

                if (partCount.containsKey(word)) {
                    partCount.put(word, partCount.get(word) + 1);
                    count++;
                } else {
                    partCount.put(word, 1);
                    count++;
                }

                while (partCount.get(word) > wordsCount.get(word)) {
                    String removeWord = splited[a];
                    partCount.put(removeWord, partCount.get(removeWord) - 1);
                    count--;
                    a += l;
                }

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

        return result;
    }
}