Find All Anagrams in a String in C++

Suppose we have a string s and a non-empty string p, we have to find all the start indices of p's anagrams in s. The strings consist of lowercase letters only and the length of both strings s and p will not be larger than 20 and 100. So for example, if s: "cbaebabacd" p: "abc", then the output will be [0, 6], at index 0, it is “cba”, and another is “bac”, these are the anagrams of “abc”.

To solve this, we will follow these steps −

• Define a map m, n := size of s, set left := 0, right := 0, counter := size of p

• define an array ans

• store the frequency of characters in p into the map m

• for right := 0 to n – 1

  • if m has s[right] and m[s[right]] is non zero, then decrease m[s[right]] by 1, decrease counter by 1 and if counter = 0, then insert left into ans

  • otherwise

    • while left < right,

      • if s[left] is not present in m, then increase counter by 1, and increase m[s[left]] by 1

      • increase left by 1

      • if m has s[right] and m[s[right]] is non zero, then decrease right by 1, and come out from the loop

    • if m has no s[left], then set left := right + 1

• return ans

Example(C++)

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } class Solution { public:    vector<int> findAnagrams(string s, string p) {       map <char, int> m;       int n = s.size();       int left = 0, right = 0;       int counter = p.size();       vector <int> ans;       for(int i = 0; i < p.size(); i++) m[p[i]]++;       for(int right = 0; right < n; right++){          if(m.find(s[right]) != m.end() && m[s[right]]){             m[s[right]]--;             counter--;             if(counter == 0)ans.push_back(left);          } else {             while(left<right){                if(m.find(s[left]) != m.end()) {                   counter++;                   m[s[left]]++;                }                left++;                if(m.find(s[right]) != m.end() && m[s[right]]){                   right--;                   break;                }             }             if(m.find(s[left])==m.end())left = right + 1;          }       }       return ans;    } }; main(){    Solution ob;    print_vector(ob.findAnagrams("cbaebabacd", "abc")) ; }

Input

"cbaebabacd" "abc"

Output

[0, 6, ]