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.
Example 1:
Input: s: “cbaebabacd” p: “abc”
Output: [0, 6]
Explanation: The substring with start index = 0 is “cba”, which is an anagram of “abc”. The substring with start index = 6 is “bac”, which is an anagram of “abc”. Example 2:
Input: s: “abab” p: “ab”
Output: [0, 1, 2]
Explanation: The substring with start index = 0 is “ab”, which is an anagram of “ab”. The substring with start index = 1 is “ba”, which is an anagram of “ab”. The substring with start index = 2 is “ab”, which is an anagram of “ab”.
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int>store; int slen=s.size(); int plen=p.size(); int check[26]={0}; for(char i:p) { check[i-'a']++; } for(int j=0;j<plen-1;j++) { check[s[j]-'a']--; } for(int i=0;i<=(slen-plen);i++) { check[s[i+plen-1]-'a']--; int k=0; for(;k<26;k++) { if(check[k]!=0) break; } if(k>=26) store.push_back(i); check[s[i]-'a']++; } return store; } };