Anagram Difference

Posted: 20 Oct, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given two strings, let's say 'STR1' and 'STR2' of equal lengths. You are supposed to return the minimum number of manipulations required to make the two strings anagrams.

Note:
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase. We can generalise this in string processing by saying that an anagram of a string is another string with the same quantity of each character in it, in any order.
Example:
String “eat” and “ate” are anagram to each other but string “buy” and “bye” are not.
Input Format:
The first line contains an integer 'T', which denotes the number of test cases. 

The first line of each test case contains the first string 'STR1' having lowercase English alphabets.

The second line of each test case contains the second string 'STR2' having lowercase English alphabets.
Output Format:
For each test case, print an integer denoting the minimum number of manipulations required to make 'STR1' and 'STR2' strings anagram.
Note:
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints :
1<= T <= 100
1<= N <= 5*10^3

Where 'N' is the length of strings 'STR1' and 'STR2'.

Time limit: 1 sec
Approach 1

The straightforward intuition is that, loop over all characters in any one given string and search for each character into the other string. If the character of the first string exists into the second string, then make it ‘#’ so that we will not be able to include this character again, and if the character does not exist then increment the count. 

 

The Steps are as follows:

 

  1. Iterate over all characters of ‘STR1’ and search it into ‘STR2’. Let’s for any ‘i’-th character, if ‘STR1[i]’ exists in ‘STR2[j]’ then make ‘STR2[j]’ to’#’, where ‘j’ is the index of 'STR2' at which ‘STR1[i]’ is found. Otherwise, increment the count of anagram difference let’s say 'minAnagramDiff' because we have to at least change ‘STR1[i]’ or ‘STR2[j]’.
  2. Return the ‘minAnagramDiff’.
Try Problem