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.

Sliding Window - Fixed#

Since an anagram of p has the same character frequencies, the idea is to slide a window of exactly p.size() characters across s and check whether the frequency counts match at each position. Two fixed-size arrays of length 26 track character counts — one for p (built once) and one for the current window of s (updated incrementally by adding the incoming character and removing the outgoing one). Comparing two 26-element arrays is O(26) = O(1), so the overall scan stays O(n). No sorting or hash maps are needed; the alphabet-size arrays act as a perfect fingerprint for the window.

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        int sSize = s.size();
        int pSize = p.size();

        if(pSize > sSize)
            return result;

        vector<int> freqP(26), freqS(26);

        for(int i=0;i<pSize;i++){
            freqP[p[i]-'a']++;
            freqS[s[i]-'a']++;
        }

        if(freqP == freqS)
            result.push_back(0);

        for(int i = pSize; i < sSize; i++ ){
            freqS[s[i]-'a']++;
            freqS[s[i-pSize]-'a']--;

            if(freqP == freqS)
                result.push_back(i - pSize + 1);
            
        }
        return result;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)