Day 17 of 31-Day May LeetCode Challenge

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:
    
    bool hashEquals(int a[], int b[]){
        for(int i=0;i<26;++i) if(a[i]!=b[i]) return false;
        return true;
    }
    
    vector<int> findAnagrams(string s, string p) {
        
        vector<int> result;
        int m = s.size(), n = p.size();
        if(m<n) return result;
        
        
        //method 1 : sliding window + hash
        //O(m+n) time & O(n) space, where m is size of string s & n is size of string p
        int patt[26] = {0};
        for(int i=0;i<n;++i) ++patt[p[i]-'a'];
        
        int text[26] = {0};
        for(int i=0;i<n;++i) ++text[s[i]-'a'];
        if(hashEquals(patt, text)) result.push_back(0);
        
        for(int i=0;i<m-n;++i){
            --text[s[i]-'a'];
            if(i+n<m) ++text[s[i+n]-'a'];
            if(hashEquals(patt, text)) result.push_back(i+1);
        }
        return result;
    }
};