Minimum Number of Steps to Make Two Strings Anagram

Problem Statement

In the problem, you are given two strings, s and t, both of which are of the same length. The purpose is to transform string t into an anagram of string s by performing a series of character replacements. A step in this process involves selecting any character from string t and replacing it with another character. You are required to determine the minimum number of such replacements needed to make t an anagram of s. An anagram of a string is another string that contains the same characters, possibly in a different order but with the exact same frequency for each character.

Examples

Example 1

Input:

s = "bab", t = "aba"

Output:

1

Explanation:

Replace the first 'a' in t with 'b', t = "bba" which is an anagram of s.

Example 2

Input:

s = "vultrdev", t = "practice"

Output:

5

Explanation:

To make t an anagram of s, you need to replace 5 characters.
For instance, replace 'p', 'a', 'c', 'i', 'e' with 'v', 'u', 'l', 'd', 'v'.

Example 3

Input:

s = "anagram", t = "mangaar"

Output:

0

Explanation:

"anagram" and "mangaar" are anagrams already. No replacements needed.

Constraints

• 1 <= s.length <= 5 * 10⁴
• s.length == t.length
• s and t consist of lowercase English letters only.

Approach and Intuition

The solution to transforming t into an anagram of s efficiently revolves around counting the differences in character frequencies between the two strings. Here's a structured approach, based on the examples provided:

1. Character Frequency Count: First, count how many times each character appears in both strings s and t. This can be efficiently done using an array of size 26 (since there are 26 lowercase English letters), where each index represents a character ('a' to 'z').

2. Calculate Differences: For each character from 'a' to 'z', compute the difference in counts between s and t. These differences will indicate how many characters in t need to be replaced to match the frequency in s.

3. Summing Up the Changes: Sum up all the positive differences calculated in the previous step. A positive difference for a character means that t has fewer instances of that character compared to s, and this number represents how many replacements you need to make t increase its count of that particular character.

4. Edge Case - Immediate Anagrams: If the sum of differences is zero, it means t is already an anagram of s, and no replacements are needed.

Example Analysis:

• Example 1 (s = "bab", t = "aba"): Only one replacement is required to match frequencies exactly.

• Example 2 (s = "vultrdev", t = "practice"): Character frequency mismatches in 5 positions, requiring 5 replacements.

• Example 3 (s = "anagram", t = "mangaar"): These are already anagrams, needing 0 replacements.

This character frequency-based approach runs in linear time, O(n), with constant space, making it both efficient and scalable for the given constraints.

Solutions

class Solution {
public:
    int minSteps(string s, string t) {
        int charDiff[26] = {0};
        for (int i = 0; i < s.length(); i++) {
            charDiff[t[i] - 'a']++;
            charDiff[s[i] - 'a']--;
        }

        int min_changes = 0;
        for (int i = 0; i < 26; i++) {
            if (charDiff[i] > 0) {
                min_changes += charDiff[i];
            }
        }
        
        return min_changes;
    }
};

class Solution {
    public int minimumSteps(String str1, String str2) {
        int[] freq = new int[26];
        // Calculate frequency difference between str2 and str1
        for (int i = 0; i < str1.length(); i++) {
            freq[str2.charAt(i) - 'a']++;
            freq[str1.charAt(i) - 'a']--;
        }

        int totalSteps = 0;
        // Sum positive differences (more characters in str2)
        for (int i = 0; i < 26; i++) {
            totalSteps += Math.max(0, freq[i]);
        }

        return totalSteps;
    }
}