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:**

**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:

- Set table1[26]={0} to store frequencies for string
*s* - Set table2[26]={0} to store frequencies for string
*t* -
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

- table1[i]=table2[i]

Then no need to do anything as we need minimum no of conversion - table2[i]>table1[i]

That means stringhas more number of same characters than in string*t*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)*s.* - table2[i]<table1[i]

That means stringhas less number of same characters than in string*t*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)*s.*

**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

**is greater than**

*t***then we need to convert the extra characters which have deficiency string**

*s***.**

*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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions