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[26] = {0}, count2[26] = {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;
}
Try It

 


Next > < Prev
Scroll to Top