Find minimum number of deletions required to make a string an anagram in C++

In this tutorial, we are going to learn about converting a lowercase string into an anagram. Then we will find minimum number of deletions required to make a string an anagram in C++. An anagram of a string is a new string formed by rearranging the letters of a given string. For example, the anagram to the string “dog” may be god, dog, gdo. Suppose we are given a string x="codespeedy" and another string y="codingspeeedy", we can make string y an anagram of x by deleting i,n,g from y. Hence the number of deletions is 3.

The idea to find a solution to this problem is by using a hashing technique. Hashing will enable us to keep track of all alphabets present in the strings along with the frequency of each alphabet.

Approach:

• Declare a hash array for each string.
• The size of the hash arrays must be 26  i.e one index for each alphabet.
• Initialize the frequency of all alphabets to 0 in the hash array.
• Iterate over the strings separately and update the frequency of each alphabet in the strings.
• Now for all 26 alphabets, check the difference in the frequency and add this difference.
•  The difference in the frequency of each alphabet in both strings is the residual alphabet.
• We have to remove these residual alphabets to get an anagram.

C++ program to find the number of deletions required to make a string an anagram.

#include<iostream>
#include<cstring>
using namespace std;
int main()
{

    int count=0;   //Variable to count no. of deletion
    string s1,s2;
        int b[26]={0},c[26]={0};        //Declaration of hash array and initialising the 
                                        //frequency of all 26 alphabets to zero
        cout<<"Enter first string"<<endl;
        cin>>s1;
        cout<<"Enter second string"<<endl;
        cin>>s2;
        for(int i=0;i<int(s1.length());i++)
        {
            b[s1[i]-97]++;               //iterating over the string to 
                                          //calculate frequency of characters
        }
         for(int i=0;i<int(s2.length());i++)
        {
            c[s2[i]-97]++;              
        }
        for(int i=0;i<26;i++)
        {
            count=count+abs(b[i]-c[i]);   //counting residual characters 
                                           //to be removed
        }
         cout<<"The number of deletions are : ";
        cout<<count<<endl;

}

Output:

Enter first string
codespeedy
Enter second string
codingspeeedy
The number of deletions are : 3

Time complexity:

the time complexity will be O(n). Where n is the length of the string.