> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/sliding-window/static-size/find-all-anagrams-in-a-string.md).

# Find All Anagrams in a String

https\://leetcode.com/problems/find-all-anagrams-in-a-string/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.

## Thoughts

找出所有p的permutation在s中出现的起始位置。维持p大小的静态窗口在s中前移，检查窗口是否是p的permutation。检查是否permutation可以维持一个freq map，当字符对应的值为负数表欠缺，正数表超出，0时刚好。cnt记录窗口内能用作p的permutation的字符数，当r扩张时，检查之前freq\[r]是否在欠缺状态，是的话cnt++；在剔除l时，同理检查freq\[l]是否在欠缺状态或刚好的状态，是的话cnt--；当cnt == p.len说明窗口内所有元素都用作了permutation，即一个所找结果。

## Code

```cpp
/*
 * @lc app=leetcode id=438 lang=cpp
 *
 * [438] Find All Anagrams in a String
 */

// @lc code=start
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if (s.length() < p.length()) return res;
        vector<int> freq(26, 0);
        int l = 0, r = 0, cnt = 0, N = p.length();
        for (const auto c : p) --freq[c - 'a']; 
        for (; r < N; ++r) {
            const auto k = s[r] - 'a';
            if (freq[k] < 0) ++cnt;
            ++freq[k];
        }
        if (cnt == N) res.push_back(l);
        while (r < s.length()) {
            const auto k = s[r] - 'a', l = s[r - N] - 'a';
            if (freq[k] < 0) ++cnt;
            ++freq[k];
            if (freq[l] <= 0) --cnt;
            --freq[l];
            if (cnt == N) res.push_back(r - N + 1);
            ++r;
        }
        return res;
    }
};
// @lc code=end


```

## Analysis

时间复杂度O(n).