## Description

https://leetcode.com/problems/find-all-anagrams-in-a-string/

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 * 10`

^{4}`s`

and`p`

consist of lowercase English letters.

## Explanation

Iterate the string s with a pointer i and find out all the positions where s[i: i+len(p)] has the same counter as string p.

## Python Solution

```
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
results = []
p_set = collections.Counter(p)
len_p = len(p)
for i in range(len(s) - len_p + 1):
sub = s[i : i + len_p]
if collections.Counter(sub) == p_set:
results.append(i)
return results
```

- Time Complexity: O(N).
- Space Complexity: O(N).