class Solution {
    // 这一题和最小覆盖子串有点相似，但是这里需要找的子串不能包括其他元素,需要加一个长度限制的检查
    // 异位词就是不同的排列方式
    // 用哈希表存储字符串中每个字符出现的次数
    // 维护一个p.length()长度的滑动窗口
    // 如果滑动窗口内的元素出现频率等于p的频率，则为字母异位词
    // 时间复杂度O(m + (n - m + 1)*26)
    // 改进的时间复杂度O(m + n)
    public List<Integer> findAnagrams(String s, String p) {
        // List<Integer> res = new ArrayList();
        // int[] pCount = new int[26];
        // for (int i = 0; i < p.length(); i++) {
        //     pCount[p.charAt(i) - 'a']++;
        // }
        // int left = 0; int right = 0;
        // int[] sCount = new int[26] ;
        // while (right < s.length()) {
        //     if(right - left + 1 > p.length()) {
        //         sCount[s.charAt(left) - 'a']--;
        //         left++;
        //     }
        //     sCount[s.charAt(right) - 'a']++;
        //     if(right - left + 1 == p.length()) {
        //         boolean isEqual = true;
        //         for (int i = 0; i < 26; i++) {
        //             if(pCount[i] != sCount[i]) {
        //                 isEqual = false;
        //                 break;
        //             }
        //         }
        //         if (isEqual) {
        //             res.add(left);
        //         }
        //     }
        //     right++;
        // }
        // return res;
       List<Integer> res = new ArrayList<>();
       int sLen = s.length(), pLen = p.length();
       if (sLen < pLen) {
            return res;
       }
       HashMap<Character, Integer> hs = new HashMap<>();
       for (int i = 0; i < pLen; i++) {
            char c = p.charAt(i); 
            hs.put(c, hs.getOrDefault(c, 0) + 1);
       }
       int required = hs.size(), current = 0;
       HashMap<Character, Integer> window = new HashMap<>();
       int left = 0, right = 0;
       while (right < sLen) {
            char word = s.charAt(right);
            if (hs.containsKey(word)) {
                window.put(word, window.getOrDefault(word, 0) + 1);
                if (window.get(word).equals(hs.get(word))) {
                    current++;
                }
            }
            while (right - left + 1 >= pLen) {
                char tmp = s.charAt(left);
                if (current == required) {
                    res.add(left);
                }
                if (hs.containsKey(tmp)) {
                    if (window.get(tmp).equals(hs.get(tmp))) {
                        current--;
                    } 
                    window.put(tmp, window.get(tmp) - 1);
                }
                left++;
            }
            right++;
       }
        return res;       
    }
}