Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- // Time Complexity:- O(max(N,26))
- // Space Complexity:- O(26)
- vector<int> findAnagrams(string s, string p) {
- int n = s.length(),m = p.length();
- // not possible for this case
- if(m>n){
- return {};
- }
- // if p is an anagram of some substring of s, then their frequency must be same
- vector<int> demand_frequency(26),substring_frequency(26),ans;
- for(auto& c:p){
- demand_frequency[c-'a']++;
- }
- for(int i=0;i<m;i++){
- substring_frequency[s[i]-'a']++;
- }
- // deviation = number of characters whose frequency aren't equal to demand frequency
- int deviation = 0;
- for(int i=0;i<26;i++){
- deviation += (demand_frequency[i]!=substring_frequency[i]);
- }
- // fill answer for first substring of m length
- if(deviation==0){
- ans.push_back(0);
- }
- for(int i=m;i<n;i++){
- int j = s[i] - 'a'; // add the current character to current frequency array
- substring_frequency[j]++;
- // if their frequency matches now, it means previously their frequency didn't match, hence we do deviation-- in this case
- if(substring_frequency[j]==demand_frequency[j]){
- deviation--;
- }
- // if current frequency of character exceeds the demand frequency of character by exactly 1, means previously they have same frequency
- else if(substring_frequency[j]-demand_frequency[j]==1){
- deviation++;
- }
- j = s[i-m] - 'a';
- substring_frequency[j]--;
- // if their frequency matches now, it means previously their frequency didn't match, hence we do deviation-- in this case
- if(substring_frequency[j]==demand_frequency[j]){
- deviation--;
- }
- // if demand frequency of character exceeds the current frequency of character by exactly 1, means previously they have same frequency
- else if(demand_frequency[j]-substring_frequency[j]==1){
- deviation++;
- }
- // if deviation is 0, means all characters have their desired frequency
- if(deviation==0){
- ans.push_back(i-m+1);
- }
- }
- return ans;
- }
- };
Add Comment
Please, Sign In to add comment