<div>
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:
<pre>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". </pre>
Example 2:
<pre>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". </pre>
Constraints:
1 <= s.length, p.length <= 3 * 10<sup>4</sup>sandpconsist of lowercase English letters.
</div>
题目大意：
求字符串s中含p的anagram的所有初始下标
解题思路：
求某子串的频率统计，第一时间想到滑动窗口。此题较特殊，属于固定大小窗口的滑动窗口，因为p的大小是固定的，窗口大小必须和p长度一样。
解题步骤：
此题可以跟LeetCode 438一样，用两个map直接比较，不用unique_count，但时间复杂度变成nm，m为p的长度
注意事项：
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14def findAnagrams(self, s: str, p: str) -> List[int]:
char_to_count_p = collections.Counter(p)
substr_win = collections.defaultdict(int)
res = []
for i, char in enumerate(s):
substr_win[s[i]] += 1
# window: [i - len(p) + 1, i]
if i >= len(p):
substr_win[s[i - len(p)]] -= 1
if substr_win[s[i - len(p)]] == 0:
substr_win.pop(s[i - len(p)])
if substr_win == char_to_count_p:
res.append(i - len(p) + 1)
return res
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
