Home » Data Structure » Hashing Coding Problems

Minimum Number of Steps to Make Two Strings Anagram

In this article, we are going to see how to find the minimum number of steps to make two strings anagram using hashing?
Submitted by Radib Kar, on July 18, 2020

Prerequisite:

• Hashing data structure

Problem statement:

Find the minimum number of steps to make two strings Anagram. Both strings are of the same length and the lower case. At each step, you can convert any character to string t to any other character.

Example:

Example 1:
String s= "bba"
String t= "aab"

Minimum number of steps to make two strings anagram: 1
String t can be converted to "bab" 
which is anagram of string s="bba"

Example 2:
String s= "coding"
String t= "coders"

Minimum number of steps to make two strings anagram: 3
String t can be converted to "coding" which is anagram of 
string s="coding"(basically here we need to convert into same string)

Solution:

We can solve the problem by using hashing. Two strings are said to be an anagram of each other if both have the same set of characters with equal frequency.

Now since both of the string is of the same length it's often possible to convert the string t to the string s. We can solve this by using a hashing and greedy algorithm.
Firstly we calculate two hash tables for both the strings s & t to store the frequencies for each character.

Let's say namely table1 and table2

Both the table have 26 entries corresponding to 26 lowercase letters. The hash function that is used is: f(x)=x-'a' and instead of storing the characters itself we store the frequency like below:

1. Set table1[26]={0} to store frequencies for string s
2. Set table2[26]={0} to store frequencies for string t

3. for(int i=0;i<s.length();i++)
       table1[s[i]-'a']++;
       table2[t[i]-'a']++;
   end for
   

Now after this both the table have 26 characters('a' to 'z') which have values 0(in case the character doesn't exist) or non-zero. Now, as the strings are of equal length it's guaranteed that string t can be converted so that it becomes an anagram of string s.

So for each character(index in table) there can be three cases

For i =0 to 26

1. table1[i]=table2[i]
   Then no need to do anything as we need minimum no of conversion
2. table2[i]>table1[i]
   That means string t has more number of same characters than in string s. Since in anagram both will the have same frequency for any character thus we need to convert the additional table2[i]-table1[i] to some other characters (not necessary to only one character)
3. table2[i]<table1[i]
   That means string t has less number of same characters than in string s. Since in anagram both will the have same frequency for any character thus we have a deficiency of (table1[i]-table2[i]) number of characters which need to be converted from rest of the excess characters (which found in the second)

So what is the minimum number of steps required?

It's basically 
sum(table2[i]-table1[i]) if table2[i]-table1[i]
Set Steps=0
For i=0 to 25
	If(table2[i]>table1[i])
	Steps+= table2[i]-table1[i]
End for

Or
For i=0 to 25
	If(table1[i]>table2[i])
	Steps+= table1[i]-table2[i]
End for

Both algorithms will give the same result as both are anagrams of each other. But sticking to the question we are assuming that we are converting string t following the convention that if for any character the frequency in t  is greater than s  then we need to convert the extra characters which have deficiency string t.

#include <bits/stdc++.h>
using namespace std;

int minSteps(string s, string t)
{
    int mymap1[26] = { 0 };
    int mymap2[26] = { 0 };

    for (int i = 0; i < s.length(); i++) {
        mymap1[s[i] - 'a']++;
        mymap2[t[i] - 'a']++;
    }

    int count = 0;

    for (int i = 0; i < 26; i++) {
        if (mymap2[i] > mymap1[i])
            count += mymap2[i] - mymap1[i];
    }
    return count;
}

int main()
{
    cout << "Enter string, s:\n";
    string s;
    cin >> s;

    cout << "Enter string, t:\n";
    string t;
    cin >> t;

    cout << "Minimum number of steps needed : " << minSteps(s, t) << endl;
    
    return 0;
}

Output:

RUN 1:
Enter string, s:
abb
Enter string, t:
baa
Minimum number of steps needed : 1

RUN 2:
Enter string, s:
coders
Enter string, t:
coding
Minimum number of steps needed : 3