# 438. Find All Anagrams in a String

## Medium

***

Given two strings `s` and `p`, return *an array of all the start indices of* `p`*'s anagrams in* `s`. You may return the answer in **any order**.

An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

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

**Constraints:**

* `1 <= s.length, p.length <= 3 * 104`
* `s` and `p` consist of lowercase English letters.

```python
from collections import defaultdict
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # What a rhyme we got here ana & pana :D
        ana = defaultdict(int)
        pana = defaultdict(int)
        result = []
        length = len(p)
        for char in list(s[:length]):
            ana[char] = ana[char] + 1
        for char in list(p):
            pana[char] = pana[char] + 1
        if ana == pana:
            result.append(0)
        oldIndex = 0
        for index in range(length, len(s)):
            ana[s[oldIndex]] = ana[s[oldIndex]] - 1
            oldIndex += 1
            ana[s[index]] = ana[s[index]] + 1
            # print(oldIndex,ana,pana)
            if self.compare(ana,pana):
                result.append(oldIndex)
        return result
        
    def compare(self, a,b):
        akeys = a.keys()
        for key,value in b.items():
            if a[key] == 0:
                return False
            elif key not in akeys:
                return False
            elif a[key] != b[key]:
                return False
        return True
```