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


Reading Time - 2 mins

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

 

READ  Perform String Shifts Leetcode
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions