给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 10⁴

• s 和 p 仅包含小写字母

要找到字符串 s 中所有 p 的异位词的子串的起始索引，我们可以利用滑动窗口结合字符计数的方法。这种方法能够有效地在 s 中定位所有 p 的异位词。

方法：滑动窗口 + 字符计数

算法步骤

1. 初始化：

• 使用两个计数器 p_count 和 s_count 来记录字符串 p 和当前窗口中字符的频次。

• 初始化结果列表 result 来存储异位词子串的起始索引。

2. 填充 p_count：

• 遍历字符串 p，将每个字符的出现次数记录在 p_count 中。

3. 滑动窗口遍历 s：

• 将当前字符添加到 s_count 中，增加其频次。

• 检查当前窗口的大小是否等于 len(p)：

• 右移窗口的右指针 right。

• 比较 s_count 和 p_count，如果相等，说明找到了一个异位词，记录其起始索引 left。

• 移动左指针 left，并减少对应字符在 s_count 中的频次。

• 如果等于：

• 设置窗口大小为 p 的长度 len(p)。

• 遍历字符串 s，使用一个长度为 len(p) 的滑动窗口：

4. 返回结果：

• 返回结果列表 result，包含所有异位词子串的起始索引。

算法实现

下面是用 Python 实现的代码：

from collections import Counter

def find_anagrams(s, p):
    # 记录p中的字符频次
    p_count = Counter(p)
    # 记录当前窗口中字符频次
    s_count = Counter()
    result = []
    # 窗口的左指针
    left = 0
    # 遍历字符串s
    for right in range(len(s)):
        # 增加当前字符到窗口中
        s_count[s[right]] += 1
        # 窗口大小大于p时，缩小窗口
        if right - left + 1 > len(p):
            # 移除左指针字符的频次
            s_count[s[left]] -= 1
            if s_count[s[left]] == 0:
                del s_count[s[left]]
            # 左指针右移
            left += 1
        # 窗口大小等于p时，检查异位词
        if right - left + 1 == len(p) and s_count == p_count:
            result.append(left)
    
    return result

# 示例
s = "cbaebabacd"
p = "abc"
result = find_anagrams(s, p)
print("异位词子串的起始索引:", result)

示例

• 输入：s = "cbaebabacd", p = "abc"

• 输出：[0, 6]

解释

在这个例子中，"cba" 和 "bac" 是 s 中的两个子串，它们都是 p = "abc" 的异位词。

复杂度分析

• 时间复杂度：O(n + m)，其中 n 是字符串 s 的长度，m 是字符串 p 的长度。我们需要遍历 s 一次，并对 p 构建计数器。

• 空间复杂度：O(m)，其中 m 是字符串 p 的长度。我们使用两个计数器来存储字符频次。

这种方法利用滑动窗口和字符计数器，能够高效地找到所有异位词子串的起始索引