Anagram Difference
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
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:
- 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]’.
- Return the ‘minAnagramDiff’.
So the intuition behind this approach is, We will first store the frequency of any one string, and then we go for each character in the other’s string, and we decrease the frequency by one. Let’s say we have stored the frequencies into ‘FREQ’, where ‘FREQ’ is the array of length 26 and initially ‘FREQ’ contains 0 for all characters. Iterate over all characters of other string and decrease the frequency by one corresponding to stored frequencies of that character.
In the end, we have the difference in frequencies between the first string and the second string into the ‘FREQ’. We will store the sum of absolute frequencies difference from ‘FREQ’. So we can change half of the mismatched characters of the first string to the required character for the second string, and we can change half of the mismatched characters of the second string to the required character for the first string so that they become Anagram.
The steps are as follows:
- Make an array of the size 26 to store the frequencies of characters, initially, it is containing 0. Let’s say ‘FREQ’.
- Iterate over all characters of the first string, i.e. 'STR1’ and store the frequencies of characters.
- Iterate over all characters of the second string i.e. ‘STR2’ and decrease the frequency of characters from ‘FREQ’.
- Now calculate the sum of absolute frequency of all 26 characters. Let’s say 'freqDiff'.
- Return ('freqDiff' / ‘2’), because we can change half of the mismatched character from 'STR1' to the required character for ‘STR2’ and we can change half of the mismatched character from 'STR2' to the required character for ‘STR1’.
