Remove Minimum Characters so that Two Strings Become Anagrams

Difficulty Level Easy
Frequently asked in Amazon FreeCharge
Anagram StringViews 4566

Problem Statement

In the “Remove Minimum Characters so that Two Strings Become Anagrams” problem we have given two input strings. Find the minimum number of_characters to be removed from these two strings such that, they become anagrams.

Input Format

The first line containing a string “s”.

The second line containing a string “t”.

Output Format

Print an integer value n which represents the minimum_number of characters to be removed from these two strings such that, they become anagrams.

Constraints

  • 1<=|s|,|t|<=10^6
  • s[i],t[j] must be a lower case English alphabet, where i,j represent the character at ith, jth position in s, t.

Example

hfgba
bgja
3

Explanation:  Here, Remove h, f from string “s” and j from string “t”. So, we removed 3 characters to make both the strings equal.

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 the 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.

Implementation

C++ Program to Remove Minimum Characters so that Two Strings Become Anagrams

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s,t;
    cin>>s>>t;
    int count1[26], count2[26];
    memset(count1,0,sizeof(count1));
    memset(count2,0,sizeof(count2));
    for (int i=0; i<s.length(); i++)
    {
        count1[s[i]-'a']++;
    }
    for (int i=0; i<t.length(); i++)
    {
        count2[t[i]-'a']++;
    }
    int ans=0;
    for(int i=0;i<26; i++)
    {
        ans+=abs(count1[i]-count2[i]);
    }
    cout<<ans<<endl;
    return 0;
}

Java Program to Remove Minimum Characters so that Two Strings Become Anagrams

import static java.lang.Math.abs;
import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                String t = sr.next();
                int count1[] = new int[26];
                int count2[] = new int[26];
                for(int i=0; i<26; i++)
                {
                    count1[i]=0;
                    count2[i]=0;
                }
                for (int i=0; i<s.length(); i++)
                {
                    count1[s.charAt(i)-'a']++;
                }
                for (int i=0; i<t.length(); i++)
                {
                    count2[t.charAt(i)-'a']++;
                }
                int ans=0;
                for(int i=0;i<26; i++)
                {
                    ans+=abs(count1[i]-count2[i]);
                }
                System.out.println(ans);
  } 
} 

tutorialcupisgoodplaceforlearning
youcanpracticeasmuchasyoucan
27

Complexity Analysis to Remove Minimum Characters so that Two Strings Become Anagrams

Time Complexity

O(n) where n is the maximum of the length of s, t. Here we traverse the whole string and count the frequency of each character in both strings which takes linear time. Then add the difference in the frequencies to the result.

Space Complexity

O(1) because here we only use two arrays of size 26 which is very small if the value of n is big. So, we can say the space complexity is constant here.

Translate »