438. Find All Anagrams in a String

LeetCode

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.

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        int left = 0, right = 0;

        unordered_map<char, int> window;
        unordered_map<char, int> need;
        for (char c : p) need[c]++;
        
        int matchChar = 0;
        while (right < s.size()) {
            char r = s[right];
            if (need.count(r)) {
                window[r]++;
                if (window[r] == need[r]) {
                    matchChar++;
                }
            }
            right++;

            while (matchChar == need.size()) {
                if (right - left == p.size()) {
                    res.push_back(left);
                }
                char l = s[left];
                if (need.count(l)) {
                    window[l]--;
                    if (window[l] < need[l]) {
                        matchChar--;
                    }
                }
                left++;
            }
        }
        return res;
    }
};