C++: Find All Anagrams in a String

Thought Process

To find all anagrams of string 'p' in string 's', we use a sliding window approach with two frequency hashes. We first create a frequency hash for 'p'. Then, we slide a window of size p.size() over 's', maintaining a frequency hash for the current window. If the frequency hash of the window matches the frequency hash of 'p', we record the starting index of the window. This ensures we efficiently find all anagram's starting indices. 

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {

        vector<int> ans;
        if(p.size() > s.size())
            return ans;

        vector<int> pHash(26,0);
        vector<int> sHash(26,0);

        for(int i=0;i<p.size();i++)
            pHash[p[i]-'a']++;

        int start=0,end=0;

        while(end<p.size()){

            sHash[s[end]-'a']++;
            end++;
        }
        if(pHash==sHash)
            ans.push_back(0);

        while(end<s.size()){

            sHash[s[end]-'a']++;
            sHash[s[start]-'a']--;
        
            end++;
            start++;

            if(pHash==sHash)
                ans.push_back(start);
        }
        return ans; 
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through 's' once, making it linear in time complexity.

Space Complexity: O(1)

The algorithm uses fixed-size frequency hashes, ensuring constant space usage.

Code copied!