leetcode-go/leetcode/hard/30.substring-with-concatenation-of-all-words.java

import java.util.*;

class Solution {
    class Frequency {
        int val;

        Frequency(int val) {
            this.val = val;
        }
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int l, m, n;
        if ((l = s.length()) == 0 || (m = words.length) == 0 || (n = words[0].length()) == 0)
            return res; // String is empty or word list is empty or each word is empty
        HashMap<String, Frequency> map = new HashMap<>();
        for (String word : words) {
            Frequency freq = map.get(word);
            if (freq == null) map.put(word, new Frequency(1));
            else freq.val++;
        } // Count the frequency of each word in the word list
        for (int i = 0; i < n; i++) { // Shift one character a time
            HashMap<String, Frequency> window = new HashMap<>();
            int begin = i, count = 0; // Begin of window, count of words in the window
            for (int j = i; j < l - n + 1; j += n) {
                String word = s.substring(j, j + n);
                Frequency target = map.get(word);
                if (target == null) { // Not in the word list, clear window & reset begin
                    window.clear();
                    begin = j + n;
                    count = 0;
                    continue;
                }
                Frequency occur = window.get(word); // Move right
                if (occur == null) {
                    occur = new Frequency(1);
                    window.put(word, occur);
                } else {
                    occur.val++;
                }
                if (occur.val <= target.val) count++;
                while (target.val < occur.val) { // Move left
                    String remove = s.substring(begin, begin + n);
                    begin += n;
                    if (remove.equals(word)) {
                        occur.val--;
                    } else {
                        Frequency freq = window.get(remove);
                        freq.val--;
                        count--;
                    }
                }
                if (count == m) res.add(begin);
            }
        }
        return res;
    }
}