Minimum Steps Needed To Make Two Strings Of Equal Length Anagrams


What is an Anagram ?
An anagram is a string of letters formed by rearranging the letters of another string.
Note : The count of each letter in the newly formed string is same as the count of each letter in the original string.

Example : Listen & Silent are both anagrams.


Algorithm : Minimum steps required to make anagrams

Step 1. Keep count of each letter in the first string in an array.
Step 2. For each letter c in the second string, do the following
            If (Count of c in the array is greater than 0) i.e the character c in the second string also exists in the first string.
                Reduce the character count of c in the array by 1. i.e Cancel out the matching letters.
Step 3. Iterate through the array and add the leftover characters counts.
            These are the non-matching characters preventing the 1’st and 2’nd strings to become anagrams of each other.


Example: Consider two strings xyzozyz and string oohmyex.
An array is used to store the count of each character in the 1’st string xyzozyz.
When we iterate through each character of the 2’nd string oohmyex, we see if it exists in the array and if it does we decrement its count. Thus we are matching the characters in the 1’st and 2’nd string. The non-matching characters i.e the remaining count is the minimum number of steps needed to make 2’nd string anagram of the 1’st string and vice-versa.

Thus 4 steps are needed to make oohmyex anagram of xyzozyz.

Make_Anagrams



Java

Java : Counting minimum number of steps needed to make two strings of equal length anagrams


C++

C++ : Minimum steps needed to make two strings of equal length anagrams


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.