Minimum Number of Steps to Make Two Strings Anagram Leetcode Solutions

Difficulty Level Easy
Frequently asked in Amazon Bloomberg Citrix Microsoft Twitter
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions StringViews 3661

Problem Statement

In this problem, we are given two strings ‘s’ & ‘t’ consisting of lower-case English characters. In one operation, we can choose any character in string ‘t’ and change it to some other character. We need to find the minimum number of such operations to make ‘t’ an anagram of ‘s’.

Example

s = "bab", t = "aba"
1
s = "leetcode", t = "practice"
5

Minimum Number of Steps to Make Two Strings Anagram

Approach

It is clear that the characters that are the same in both the strings do not require any operations(as we need their simultaneous presence, not the same order). The important part is to understand how can we solve for the rest of the charcters.

Let say we first cleared all the characters in string ‘s’ that match to some character in string ‘t’, and then deleted those corresponding characters in the string ‘t’. Example s = “ginny”, t = “harry”. After removing matching characters in both the strings, s = “ginn”, t = “harr”. Now, it is obvious that every character in string ‘t’ must be changed to some other character so that the characters of ‘s’ are also present in it.

Remember that we had already removed all pairs of matchings in ‘s’ and ‘t’. So, there will be no character in ‘t’ that is present in ‘s’. This can easily be implemented with the help of a hash table.

Implementation of Minimum Number of Steps to Make Two Strings Anagram Leetcode Solutions

C++ Program

#include <bits/stdc++.h>

using namespace std;

int minSteps(string s, string t) {
    unordered_map <int , int> f;
    int ans = 0;
    for(char &c : s) {
        f[c - 'a']++;
    }

    for(char &c : t) {
        f[c - 'a']--;
    }

    for(auto &c : f) {
        if(c.second != 0)
            ans++;
    }

    return ans / 2;
}

int main() {
    string s = "bab" , t = "aba";
    cout << minSteps(s , t) << endl;
    return 0;
}

Java Program

import java.util.*;
import java.io.*;
import java.util.Hashtable;
import java.util.Set;
import java.util.Iterator;

class anagrams {
    public static void main(String args[]) {
        String s = "bab" , t = "aba";
        System.out.println(minSteps(s , t));
    }

    public static int minSteps(String s , String t) {

        Hashtable <Character , Integer> f = new Hashtable<>();
        int ans = 0;
        for(char c : s.toCharArray()) {
            f.put(c , f.getOrDefault(c , 0) + 1);
        }

        for(char c : t.toCharArray()) {
            f.put(c , f.getOrDefault(c , 0) - 1);
        }

        for(char c = 'a' ; c <= 'z' ; c++) {
            if(f.containsKey(c) && f.get(c) != 0) {
                ans += Math.abs(f.get(c));
            }
        }

        return ans / 2;
    }
}
1

Complexity Analysis of Minimum Number of Steps to Make Two Strings Anagram Leetcode Solutions

Time Complexity

O(N), where N = lengths of string ‘s’ & ‘t’.

Space Complexity 

O(1), as there is a limited number of unique characters in both strings, we know that the memory space remains constant.

Translate »