[LeetCode] 438. Find All Anagrams in a String

• 這一題與 567 類似，是找 anagram 題題目，令 p 長度為 window size，即可解。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        int k = p.size();
        int n = s.size();
        if (n < k) return res;
        unordered_map<char,int> cnt1, cnt2;
        for (const auto& c : p) cnt1[c]++;
        int valid = 0;
        for (int i = 0; i < k; i++) {
            if (cnt1.count(s[i]) && ++cnt2[s[i]] == cnt1[s[i]]) valid++;
        }
        if (valid == cnt1.size()) res.push_back(0);
        for (int i = k; i < n; i++) {
            if (cnt1.count(s[i]) && ++cnt2[s[i]] == cnt1[s[i]]) valid++;
            if (cnt1.count(s[i-k]) && cnt2[s[i-k]]-- == cnt1[s[i-k]]) valid--;
            if (valid == cnt1.size()) res.push_back(i-k+1);
        }
        return res;
    }
};