## Description

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


## Solutions

### 1. Brute Force

# Time: O(nm)
# Space: O(n)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
res = []
for i in range(ns-np+1):
if self.is_anagrams(s[i:i+np], p):
res.append(i)
return res

def is_anagrams(self, s, p):
s_dict = collections.defaultdict()
p_dict = collections.defaultdict()
for ch in s:
s_dict[ch] = s_dict.get(ch, 0) + 1

for ch in p:
p_dict[ch] = p_dict.get(ch, 0) + 1

return s_dict == p_dict

# Time Limit Exceeded
# 34/36 cases passed (N/A)

# Time: O(nm)
# Space: O(n)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
p_dict = collections.defaultdict()
for ch in p:
p_dict[ch] = p_dict.get(ch, 0) + 1
res = []
for i in range(ns-np+1):
s_dict = collections.defaultdict()
for j in range(i, i+np):
s_dict[s[j]] = s_dict.get(s[j], 0) + 1
if s_dict == p_dict:
res.append(i)
else:
s_dict[s[i]] = s_dict[s[i]] - 1
if s_dict[s[i]] == 0:
s_dict.pop(s[i])
return res

# Time Limit Exceeded
# 34/36 cases passed (N/A)


### 2. Hash Table

用字符串的机器码作为下标，定义一个足够大的数组，Python 中 123 即可。

# Time: O(n)
# Space: O(1)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
if np > ns:
return []
shash, phash = [0] * 123, [0] * 123
res = []
for ch in p:
phash[ord(ch)] += 1
for i in range(np-1):
shash[ord(s[i])] += 1
for i in range(np-1, ns):
shash[ord(s[i])] += 1
if i - np >= 0:
shash[ord(s[i - np])] -= 1
if shash == phash:
res.append(i - np + 1)
return res

# 36/36 cases passed (112 ms)
# Your runtime beats 75.49 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.7 MB)