Home » Technical Interview Questions » String Interview Questions » Remove minimum characters so that two strings become anagrams

# Remove minimum characters so that two strings become anagrams

## Given two input strings, fins minimum number characters to be removed from these two strings such that, they become anagrams.

### Examples

Input : string1 = “hfgba” string2 = “bgja”

Output : 3
Here, Remove h, f from string1 and j from string2.

Time complexity : O(n)

## Algorithm

1. Traverse both the input strings.

2. Store the count of characters in string1 in array count1 and count of characters in string2 in array count2.

3. Traverse count arrays, store number of characters to be removed in result. (initialize result = 0 )

4. For all characters add differences in the frequencies to result, result = result + abs(count1[i] – count2[i]).

5. Return the final result.

## C++ Program

```#include <bits/stdc++.h>

using namespace std;

int RemoveToFormAnagram(string str1, string str2)
{
//Initialize count arrays with zeroes
int count1 = {0}, count2 = {0};
//store the frequiencies of characters in string1 in count1
for (int i=0; str1[i]!='\0'; i++)
{
count1[str1[i]-'a']++;
}
//store the frequiencies of characters in string2 in count2
for (int i=0; str2[i]!='\0'; i++)
{
count2[str2[i]-'a']++;
}
//result is the number of characters to be removed
int result = 0;
for (int i=0; i<26; i++)
{
result = result + abs(count1[i] - count2[i]);
}
return result;
}

//Main function
int main()
{
string str1 = "hfgba", str2 = "bgja";
cout<<"Minimum number of characters to be removed is: "<<RemoveToFormAnagram(str1, str2);
return 0;
}```