# LC 438. Find All Anagrams in a String

### [Problem link](https://leetcode.com/problems/find-all-anagrams-in-a-string/)

###### tags: `leedcode` `medium` `c++` `Sliding Window`

Given two strings <code>s</code> and <code>p</code>, return an array of all the start indices of <code>p</code>'s anagrams in <code>s</code>. 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:**

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

**Constraints:**

- <code>1 <= s.length, p.length <= 3 * 10⁴</code>
- <code>s</code> and <code>p</code> consist of lowercase English letters.

## Solution 1 - Sliding Window
#### C++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> cntp(26, 0);
        for (char& c: p) {
            cntp[c - 'a']++;
        }

        vector<int> ans;
        vector<int> cnts(26, 0);
        for (int i = 0; i < s.size(); i++) {
            cnts[s[i] - 'a']++;
            if (i < p.size() - 1) {
                continue;
            }
            if (cntp == cnts) {
                ans.push_back(i - p.size() + 1);
            }
            cnts[s[i - p.size() + 1] - 'a']--;
        }
        return ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
x