# 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={0},c={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.