# \[438]\[中等]\[滑动窗口] 找到字符串中所有字母异位词

## 题目描述

[438. 找到字符串中所有字母异位词](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/)

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

* 字母异位词指字母相同，但排列不同的字符串。
* 不考虑答案输出的顺序。

示例 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" 的字母异位词。
```

## 解题思路

也是标准的滑动窗口的思路. 与[\[76\]\[困难\]\[滑动窗口\] 最小覆盖子串](/garnet/suan-fa/hua-dong-chuang-kou/76-zui-xiao-fu-gai-zi-chuan.md)不同的是, 这里不再是子序列, 而是连续的子串, 因此在右指针移动时, 遇到不在`p`中的字符, 就可以直接抛弃当前窗口, 将左右指针都置为下一个位置.

同样是因为寻找的是子串, 左指针收缩的条件, 就变为了左右指针相距的长度等于`p`字符串的长度, 此时我们不能再继续移动右指针的位置, 而是应该收缩左指针. 如果当前窗口中的正好是`p`的一个排列, 就记录当前的起点(左指针); 如果不是, 就收缩一次左指针, 然后右指针继续扩张, 找到下一个满足长度的窗口进行判断.

```python
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, p_count = len(s), len(p)
        p_map = Counter(p)

        s_map, s_count = dict(), 0
        res = []
        left = right = 0
        while right < n:
            char = s[right]
            right += 1

            if char not in p_map:
                s_map.clear()
                s_count = 0
                left = right
            else:
                count = s_map.get(char, 0)
                s_map[char] = count + 1
                if count < p_map[char]:
                    s_count += 1

                while right - left == p_count:
                    if s_count == p_count:
                        res.append(left)
                    char = s[left]
                    left += 1
                    count = s_map.get(char, 0)
                    s_map[char] = count - 1
                    if count <= p_map[char]:
                        s_count -= 1
        return res
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/hua-dong-chuang-kou/438-zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-yi-wei-ci.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.