# Leetcode 438. Find All Anagrams in a String
###### tags: `leetcode` `daily`

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

# Method 1 two pointer
:::info
:bulb: **作法講解**:
1. The first step is to find the freq of all characters in s1
2. Then we maintain a window, initailly window size is 1, that means start = 0, end = 0
3. we will be continuing the below steps, untill the end of windows reaches the end of string s2,
a) increase the frequency of s2[window's end]
b) check if the frequency of the character in the current window is same as the frequecy of character in string s1,

c1)if frequency does match, then we can add the index into output,

c2) if frequency does not match, we have to change the window,
if has the freqency of any character in window bigger than the frequency of s1,
we need to move start to the next character,
until no any character, it's frequency bigger than frequency of s1.
:::

TC: O(N) SC: O(1)
:::spoiler 完整程式碼

class Solution {
public:
    bool check_cnts_over(vector<int> &cnts, vector<int> &cntp) 
    {
        for(int i = 0 ; i < cnts.size() ; i++) {
            if(cnts[i] > cntp[i]) {
                return true;
            }
        }
        return false;
    }
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> cntp(26, 0);
        vector<int> cnts(26, 0);
        vector<int> output;
        int l = 0;
        for(char c : p) {
            cntp[c-'a']++;
        }

        for(int i = 0 ; i < s.size() ; i++) {
            cnts[s[i]-'a']++;
            while(check_cnts_over(cnts, cntp)) {
                cnts[s[l]-'a']--;
                l++;
            }
            if((i - l + 1) == p.size()) {
                output.push_back(l);
            }
        }

        return output;
    }
};

:::