> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/string/substring-search/find-all-anagrams-in-a-string.md).

# 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!