Day 17 of 31-Day May LeetCode Challenge

Aanchal Patial
1 min readMay 17, 2020

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

--

--

Aanchal Patial

We never really grow up, we only learn how to act in public