Day 17 of 31-Day May LeetCode Challenge

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;
}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store