Find Minimum Number of Steps to Make Two Strings Anagram II️‍🔥

Q: What is Find Minimum Number of Steps to Make Two Strings Anagram II?

In this article, we will learn Find Minimum Number of Steps to Make Two Strings Anagram II,This free Data Structures and Algorithms tutorial for complete beginners will help you learn Data Structures and Algorithms from scratch.

Given two strings S and T, the task is to find the minimum number of steps to make S and T anagrams of each other. In one step, we can append any character to either S or T.

Example:

Input: S = “gee”, T = “eks”
Output: 4
Explanation: Append ‘k’ and ‘s’ to string S and append ‘g’ and ‘e’ to string T to make S and T anagram of each other.

Input: S = “Beginner”, T = “egesk”
Output: 0
Explanation: “Beginner” and “egesk” are anagrams.

Approach: To solve the problem, follow the below idea:

To solve this problem, the idea is to count the frequency of each character in both strings S and T. Then, calculate the difference in frequencies for each character. The sum of positive differences will give the minimum number of steps needed to make T an anagram of S.

Step-by-step algorithm:

Count the frequency of each character in both strings S and T.
For each character, calculate the difference in frequency between S and T.
Sum the positive differences to get the minimum number of steps required.

Below is the implementation of the algorithm:

C++

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

// Function to find minimum steps to make S and T anagram of
// each other
int minSteps(string S, string T)
{
    // Frequency array to store the difference between
    // frequency of characters
    int freq[26] = {};
    // For every character in S, add 1 to the frequency
    // array
    for (char ch : S) {
        freq[ch - 'a'] += 1;
    }
    // For every character in S, subtract 1 to the frequency
    // array
    for (char ch : T) {
        freq[ch - 'a'] -= 1;
    }
    // Sum of absolute difference is the required number of
    // steps
    int ans = 0;
    for (int i = 0; i < 26; i++) {
        ans += abs(freq[i]);
    }
    return ans;
}

int main()
{
    // Sample Input
    string S = "gee";
    string T = "eks";
    cout << minSteps(S, T) << endl;

    return 0;
}

Java

import java.util.*;

public class MinStepsAnagram {

    // Function to find minimum steps to make S and T
    // anagram of each other
    public static int minSteps(String S, String T)
    {
        // Frequency array to store the difference between
        // frequency of characters
        int[] freq = new int[26];

        // For every character in S, add 1 to the frequency
        // array
        for (char ch : S.toCharArray()) {
            freq[ch - 'a'] += 1;
        }

        // For every character in T, subtract 1 from the
        // frequency array
        for (char ch : T.toCharArray()) {
            freq[ch - 'a'] -= 1;
        }

        // Sum of absolute differences is the required
        // number of steps
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += Math.abs(freq[i]);
        }

        return ans;
    }

    public static void main(String[] args)
    {
        // Sample Input
        String S = "gee";
        String T = "eks";
        System.out.println(minSteps(S, T));
    }
}

// This code is contributed by Shivam Gupta

Output

Time Complexity: O(n), where n is the length of the strings S and T.
Auxiliary Space: O(1), since the size of the frequency arrays is constant (26 for each alphabet letter).