Q:

Given a string S and a word C, return the count of the occurrences of anagrams of the word in the text. Both string and word are in lowercase letter

mahmoud2506
Save to bookmark
|
2022-04-29
|
  542 
0

Count Occurrences of Anagrams

Given a string S and a word C, return the count of the occurrences of anagrams of the word in the text. Both string and word are in lowercase letter.

Examples:

 

    Input:
    S=fororfrdofr
    C=for

    Output:
    3
    
    Input:
    S=aabaabaa
    C=aaba
    
    Output:
    4
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-29
need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

    1.  Set count=0;
        For i=0:i<a.length()-b.length()+1
            IF (check(a.substr(i,b.length()),b))
            count++;
    2.  Print count

So the idea is pretty simple. What we are doing is to slide the window and check for anagrams. Window is nothing but the substring being extracted every time. Window length is equal to the word length.

To check anagrams

FUNCTION check(string a, string b)

1.  Declare a map <char, int="" style="box-sizing: border-box;"> m; //to store frequency of each character
2.  For string abuild the map
    For (int i=0;i<a.length();i++)
        m[a[i]]++;
    END FOR
3.  For string bdestruct the map.
    For (int i=0;i<b.length();i++)
        m[b[i]]--;
    END FOR
4.  If map is totally destructed that means all key has value perfectly 0 
        return true;
    Else 
        Return false.

END FUNCTION
</char,>

So this basically means, we are constructing a container using the elements of string a. Then we are destructing the map to form string b. If such formation is possible they strings are anagrams of each other.

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

bool check(string a,string b){
	//checking anagrams
	map<char,int> m;
	for(int i=0;i<a.length();i++)
		m[a[i]]++;
	for(int i=0;i<b.length();i++)
		m[b[i]]--;
	for(auto it=m.begin();it!=m.end();it++)
		if(it->second!=0)
			return false;
	return true;
}

int countNoOfAnagram(string a,string b){
	int count=0;
	//sliding window
	for(int i=0;i<a.length()-b.length()+1;i++){
		if(check(a.substr(i,b.length()),b))
			count++;
	}
	return count;
}

int main()
{
	string S,C;
	
	cout<<"Enter string S and word C\n";
	cin>>S>>C;
	
	cout<<"No of anagrams: "countNoOfAnagram(S,C)<<endl;
	
	return 0;
}

Output

Enter string S and word C
fororfrdofr
for
No of anagrams: 3

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Interview C++ coding problems/challenges | String
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given a string containing uppercase alphabets and ... >>
<< our goal is to minimize the number of bits to be f...