Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:s: "cbaebabacd" p: "abc"Output:[0, 6]Explanation:The substring with start index = 0 is "cba", which is an anagram of "abc".The substring with start index = 6 is "bac", which is an anagram of "abc".

 

Example 2:

Input:s: "abab" p: "ab"Output:[0, 1, 2]Explanation:The substring with start index = 0 is "ab", which is an anagram of "ab".The substring with start index = 1 is "ba", which is an anagram of "ab".The substring with start index = 2 is "ab", which is an anagram of "ab".

 

用sliding window模板，保存结果的判断条件是fast - slow == p.length()

time: O(n), space: O(m)　　-- n: length of s, m: length of p

class Solution {        public List
     
       findAnagrams(String s, String p) {        List
      
        res = new ArrayList<>();        if(s.length() == 0 || s.length() < p.length()) {            return res;        }                Map
       
         map = new HashMap<>();        for(char c : p.toCharArray()){            map.put(c, map.getOrDefault(c, 0) + 1);        }                int counter = map.size(), slow = 0, fast = 0;                while(fast < s.length()) {            char c = s.charAt(fast);            if(map.containsKey(c)) {                map.put(c, map.get(c) - 1);                if(map.get(c) == 0) {                    counter--;                }            }            fast++;                        while(counter == 0) {                char tempc = s.charAt(slow);                if(map.containsKey(tempc)) {                    map.put(tempc, map.get(tempc) + 1);                    if(map.get(tempc) > 0) {                        counter++;                    }                }                if(fast - slow == p.length()) {                    res.add(slow);                }                slow++;            }        }        return res;    }}