Problem of the day
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.
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.
1<= T <= 100
1<= N <= 5*10^3
Where 'N' is the length of strings 'STR1' and 'STR2'.
Time limit: 1 sec
2
except
accept
buy
bye
2
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.
2
mail
male
ninja
ninja
1
0
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.
How can you find that any character of “str1” does not exist in “str2”?
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:
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).
O(1)
Since we are not using any extra space, Thus space complexity will be O(1).