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".

Time: O(N)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        
        my_dict = {}
        res = []
        count = 0
        for char in p:
            freq = my_dict.get(char, 0)
            my_dict[char] = freq + 1
            
        for i in range(len(s)):
            char = s[i]
            if char in my_dict:
                my_dict[char] -= 1
                if my_dict[char] == 0:
                    count += 1
            
            if i >= len(p):
                start = i - len(p)
                start_char = s[start]
                if start_char in my_dict:
                    my_dict[start_char] += 1
                    if my_dict[start_char] == 1:
                        count -= 1
            # check my_dict size instead of len(p)
            if count == len(my_dict):
                res.append(i - len(p) + 1)
        return res