Algotree > Algorithms > Minimum Steps Needed To Make Two Strings Of Equal Length Anagrams

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

Program for counting minimum steps to make two strings anagrams

#include<iostream>
#include<string>
#include<vector>

using namespace std;

class Anagram {

    public:
    // Below function returns the minimum number of steps needed to make
    // two strings anagrams of each other.
    int MinimumSteps (string source, string target) {

        int letter_count[26] = {0};

        // Keep a count of each letter in the first string.
        for (int pos = 0; pos < source.size(); pos++) {
            letter_count[source[pos]-'a']++;
        }
    
        // Reduce the count of each matching letter in the second string.
        for (int pos = 0; pos < target.size(); pos++) {
            if (letter_count[target[pos]-'a'])
                letter_count[target[pos]-'a']--;
        }

        int steps = 0;
        // The left over letter count is the number of steps needed to 
        // make the second string (target) anagram of first (source).
        for(int i = 0; i < 26; i++) {
            steps += letter_count[i];
        }
        return steps;
    }
};

int main() {

    Anagram make;

    vector<string> target = {"xxx", "abab", "abcde", "oohmyex"};
    vector<string> src = {"abc", "abba", "abccc", "xyzozyz"};

    for (int i = 0; i < target.size(); i++) {                   
        cout << "\nSource : [" << src[i] << "] Target : [" << target[i] << "]" << endl;
        cout << "Minimum steps needed for making anagram : " << make.MinimumSteps (src[i], target[i]) << endl;
    }
    return 0;
}

Output

Source : [abc] Target : [xxx]
Minimum steps needed for making anagram : 3

Source : [abba] Target : [abab]
Minimum steps needed for making anagram : 0

Source : [abccc] Target : [abcde]
Minimum steps needed for making anagram : 2

Source : [xyzozyz] Target : [oohmyex]
Minimum steps needed for making anagram : 4

import java.util.List;
import java.util.Arrays;

class Anagram {

    // Below function returns the minimum number of steps needed to make
    // two strings anagrams of each other.
    public int MinimumSteps (String source, String target) {

        int letter_count[] = new int[26];

        // Keep a count of each letter in the first string.
        for (int pos = 0; pos < source.length(); pos++) {
            letter_count[source.charAt(pos)-'a']++;
        }
    
        // Reduce the count of each matching letter in the second string.
        for (int pos = 0; pos < target.length(); pos++) {
            if (letter_count[target.charAt(pos)-'a'] > 0)
                letter_count[target.charAt(pos)-'a']--;
        }

        int steps = 0;
        // The left over letter count is the number of steps needed to 
        // make the second string (target) anagram of first (source).
        for(int i = 0; i < 26; i++) {
            steps += letter_count[i];
        }
        return steps;
    }

    public static void main (String args[]) {
    
        Anagram make = new Anagram();
    
        List<String> target = Arrays.asList("xxx", "abab", "abcde", "oohmyex");
        List<String> src = Arrays.asList("abc", "abba", "abccc", "xyzozyz");
    
        for (int i = 0; i < target.size(); i++) {
            System.out.println("\nSource : [" + src.get(i) + "] Target : [" + target.get(i) + "]\n");
            System.out.println("Minimum steps needed for making anagram : " + make.MinimumSteps (src.get(i), target.get(i)));
        }   
    }   
}

Output

Source : [abc] Target : [xxx]

Minimum steps needed for making anagram : 3

Source : [abba] Target : [abab]

Minimum steps needed for making anagram : 0

Source : [abccc] Target : [abcde]

Minimum steps needed for making anagram : 2

Source : [xyzozyz] Target : [oohmyex]

Minimum steps needed for making anagram : 4