Anagram Difference

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
39 upvotes
Asked in companies
Expedia GroupCiscoAdobe

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
except
accept
buy
bye
Sample Output 1 :
2
1
Explanation Of Sample Output 1 :
In test case 1, we can change two character of  'STR1' i.e. {'e','x'} to {'a','c'} or we can change two character of  'STR2' i.e. {'a','c'} to {'e','x'}, to make string anagram. So the minimum number of manipulations to make 'STR1' and  'STR2' to anagram string will be 2.

In test case 2, we can change one character of  'STR1' i.e. {'u'} to {'e'} or we can change one character of  'STR2' i.e. {'e'} to {'u'}, to make string anagram. So the minimum number of manipulations to make  'STR1' and 'STR2' to anagram string will be 1.
Sample Input 2:
2
mail
male
ninja
ninja
Sample Output 2 :
1
0
Explanation Of Sample Output 2 :
In test case 1, we can change one character of  'STR1' i.e. {'i'} to {'e'} or we can change one character of  'STR2' i.e. {'e'} to {'i'}, to make string anagram. So the minimum number of manipulations to make  'STR1' and  'STR2' to anagram string will be 1.

In test case 2, both strings are already anagram. So we do not need to do any manipulation. So the minimum number of manipulations to make  'STR1' and  'STR2' to anagram string will be 0.
Hint

How can you find that any character of “str1” does not exist in “str2”?

Approaches (2)
Brute Force

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’.
Time Complexity

O(N^2), where ‘N’ is the length of the given string.

 

We are going to iterate ‘STR1’ and checking whether the current character exists into ‘STR2’ or not. So, in the worst case when none of the characters of string ‘STR1’ exists in ‘STR2’, then for all ‘N’ characters of ‘STR1’ will be spending ‘N’ time to search into ‘STR2’. Thus the overall time complexity will be O(N^2).

Space Complexity

O(1)

 

Since we are not using any extra space, Thus space complexity will be O(1).

Code Solution
(100% EXP penalty)
Anagram Difference
Full screen
Console