# 438. Find All Anagrams in a String

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.

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

**Thoughts**

1. Two pointer to keep track of current sliding anagram candidate window
2. Find answers by tracking current sliding window status in the anagram **map**
3. Count: # character current sliding window needs (does not have)

**Code: O(n)**

```cpp
class Solution {
    vector<int> answer;
public:
    vector<int> findAnagrams(string s, string p) {
        // first scaning throught p to construct char frequency map 
        unordered_map <char, int> map;

        for(int i = 0 ; i< p.length() ; i++){
           char key = p[i];
           ++map[key];
        }

        int left = 0, right = 0;
        int count = map.size(); // count how many char left to satisfy the anagram
        while(right < s.length()){
            char curChar = s[right];
            if(map.find(curChar) != map.end()){
                --map[curChar];
                if(map[curChar] == 0) count--; // means current sliding window already contains this character to fulfill the anagram 
            }
            right++;

            // count == 0 means there is a anagram in current sliding window,
            // we find them in the following code
            while(count == 0){
                // do 
                if(right - left == p.length()) answer.push_back(left); 

                // increment: change the count status for the next step
                char beginChar = s[left];
                if(map.find(beginChar) != map.end()){
                    // ++map[beginChar]; // for the next iteration;
                    if (++map[beginChar] > 0) count++; // means current sliding window needs this character to fulfill the anagram 
                }
                left++;
            }
        }

        return answer;
    }

};
```

**Python**

```python
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        d = collections.Counter(p)
        slow,fast, res= 0, 0, []
        count = len(d)

        while fast < len(s):
            if s[fast] in d:
                d[s[fast]]-=1
                if d[s[fast]] == 0:
                    count -= 1
            fast += 1

            while count == 0:
                if fast - slow == len(p):
                    res.append(slow)
                if s[slow] in d:
                    d[s[slow]] +=1
                    if d[s[slow]] > 0:
                        count += 1

                slow += 1

        return res
```

**C++ Template**

```cpp
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector <int> map (128, 0);
        int count = p.size(), slow = 0 , fast = 0;
        vector<int> res;
        for (auto c: p) ++map[c];
        while (fast < s.size()){
            if(map[s[fast++]]-- > 0) count--;
            while(count == 0){
                if(fast - slow == p.size()) res.push_back(slow);
                if (map[s[slow++]]++ == 0)count++;
            }
        }
        return res;
    }
};
```

**Java Template**&#x20;

```
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int map [] = new int [128];
        int count = p.length(), slow = 0, fast = 0;

        List<Integer> res = new ArrayList<>();

        for (char c : p.toCharArray()) map[c] ++;

        char Chars [] = s.toCharArray();

        while(fast < Chars.length){
            if(map[Chars[fast++]]-- > 0) count--;

            while(count == 0){
                if(fast - slow == p.length()) res.add(slow);

                if(map[Chars[slow++]]++ == 0) count++;
            }
        }

        return res;
    }
}
```

**Python Template**

```python
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        m = collections.defaultdict(int)
        cnt, slow, fast, res = len(p), 0, 0, []

        for c in p: m[c] +=1

        while fast < len(s):
            if(m[s[fast]] > 0):
                cnt-=1
            m[s[fast]] -=1 
            fast+=1

            while cnt == 0:
                if fast - slow == len(p): res.append(slow)

                if m[s[slow]] == 0:
                    cnt += 1
                m[s[slow]] += 1
                slow += 1

        return res
```

Special thanks:[ LeetCode Discussion Forum](https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/) for the reference!


---

# 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://code.taozirui.com/lc/string/substring-search/find-all-anagrams-in-a-string.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.