###### tags: `Leetcode` `medium` `sliding window` `python` `c++` `Top 100 Liked Questions`

# 438. Find All Anagrams in a String

## [題目連結:] https://leetcode.com/problems/find-all-anagrams-in-a-string/

## 題目:
Given two strings ```s``` and ```p```, return an array of all the start indices of ```p```'s anagrams in ```s```. 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".

## 解題想法:
* 此題為，給兩個字串s、p
* 在s中找到p的所有anagrams的起始位置
* anagrams為字符種類各數均相同，順序可以不同
* Sliding Window:
* **slide Window size為 len( p )**
* 需要參數:
* res=[] :存anagrams start position
* cur_tmp=Counter() :統計目前拜訪的範圍中出現的字符與其次數
* python用collections.Counter()
* 也可以單純使用list[0] * 26 紀錄每個字母，因為題目規定一定是小寫，所以全部-'a'即可，(a為ASCII 97)
* countP=Counter(p): 統計p的字符種類與其次數，用來比較
* head=0
* tail=0
* Step1:
* 每次將s[tail]紀錄
* cur_tmp[s[tail]]+=1
* Step2: **若目前長度(tail-head+1)等於len(p)，進入判斷**
* 若cur_tmp==countP，表示長度夠且符合anagrams
* res.append(head)，將head紀錄於最終解
* **將head右移，讓後面tail能繼續遍歷**
* cur_tmp[s[head]]-=1
* 若cur_tmp[s[head]]為0，則需刪除
* head+=1
* Step3:
* tail+=1

## Python:

from collections import Counter
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        res=[]  #存start pos
        if len(s)<len(p):
            return res
        cur_tmp=Counter()
        countP=Counter(p)
        #slide winodw為len(p)
        head=0
        tail=0
        while tail<len(s):
            cur_tmp[s[tail]]+=1
            if (tail-head+1)==len(p):  
                if cur_tmp==countP:  #長度夠且符合
                    res.append(head)
                #將head右移 給後面tail繼續找
                cur_tmp[s[head]]-=1
                if cur_tmp[s[head]]==0: #若為幽靈人口要刪除
                    del cur_tmp[s[head]]
                head+=1
            tail+=1
            print(cur_tmp,res)
        return res

s = "cbaebabacd"
p = "abc"
result=Solution()
ans=result.findAnagrams(s,p)
print(ans)

## Python: use array to store 26 letters

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        head=0
        tail=0
        res=[]
        countTmp=[0]*26
        countP=[0]*26
        for val in p:
            countP[ord(val)-ord('a')]+=1
        while tail<len(s):
            countTmp[ord(s[tail])-ord('a')]+=1
            if (tail-head+1)==len(p):
                if countTmp==countP:
                    res.append(head)
                countTmp[ord(s[head])-ord('a')]-=1
                head+=1
            tail+=1
        return res

## C++:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int head=0, tail=0, lenS=s.size(), lenP=p.size();
        vector<int> res;
        vector<int> countTmp(26, 0), countP(26, 0);
        for (auto val: p){
            countP[val-'a']+=1;
        }
        while (tail<lenS){
            countTmp[s[tail]-'a']+=1;
            if ((tail-head+1)==lenP){
                if (countTmp==countP)
                    res.push_back(head);
                countTmp[s[head]-'a']-=1;
                head+=1;
            }
            tail+=1;
        }
        return res;
    }
};