Problem Description

Given two strings, s and t, both of the same length and consisting of lowercase English letters, you are asked to determine the minimum number of steps required to make t an anagram of s.

In one step, you can choose any character in t and replace it with any other character.

• You must transform t so that after all replacements, it is an anagram of s (i.e., both strings have the same character counts for each letter).
• Each replacement can only affect one character at a time.
• The strings are guaranteed to be the same length.

Thought Process

The brute-force way to approach this problem would be to try all possible replacements in t until it matches s as an anagram, but this would be highly inefficient. Instead, we need a smarter way to compare the character compositions of s and t.

Since the only allowed operation is replacement, and we only care about character counts (not order), the problem boils down to: for each character, how many more times does it appear in s than in t? For every such surplus in s, we need at least that many replacements in t to "cover" the difference.

This leads us to use frequency counts (hash maps or arrays) to efficiently compare the two strings, instead of checking all permutations.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Count Character Frequencies:
   • Count how many times each letter appears in s and in t.
   • We can use an array of length 26 (for each lowercase English letter) or a hash map for this.
2. Calculate Differences:
   • For each letter, if s has more occurrences than t, we need to replace some letters in t to make up the difference.
   • Sum up all such positive differences across all letters. This gives the minimum number of replacements needed.
3. Return the Result:
   • The total sum is the answer: the minimum number of steps to make t an anagram of s.

We use arrays (or hash maps) for counting because lookups and updates are O(1), making the process efficient.

Example Walkthrough

Let's use the example:
s = "bab", t = "aba"

1. Count characters:
   • s: 'a' appears 1 time, 'b' appears 2 times
   • t: 'a' appears 2 times, 'b' appears 1 time
2. Calculate differences:
   • For 'a': s has 1, t has 2 → no replacement needed (since t has enough 'a's)
   • For 'b': s has 2, t has 1 → need 1 more 'b' in t
3. Total replacements needed: 1
4. So, change one 'a' in t to 'b' to make t an anagram of s.

Time and Space Complexity

• Brute-force approach: Would involve generating all anagrams or all possible replacements, which is factorial in length (O(n!)), and is not feasible for even small strings.
• Optimized approach (using frequency counts):
  • Time Complexity: O(n), where n is the length of the strings. We scan each string once to count frequencies, and then compare the 26 possible letters.
  • Space Complexity: O(1), since the frequency arrays are of fixed size (26), regardless of input length.

Summary

The key insight is to realize that making two strings anagrams is about matching their character counts, not their order. By counting the frequency of each letter in both strings and summing up the positive differences, we can efficiently determine the minimum number of replacements needed. This approach is both elegant and optimal, avoiding the pitfalls of brute-force search.

Code Implementation

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        from collections import Counter
        count_s = Counter(s)
        count_t = Counter(t)
        steps = 0
        for c in count_s:
            if count_s[c] > count_t.get(c, 0):
                steps += count_s[c] - count_t.get(c, 0)
        return steps
      

class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> countS(26, 0), countT(26, 0);
        for (char c : s) countS[c - 'a']++;
        for (char c : t) countT[c - 'a']++;
        int steps = 0;
        for (int i = 0; i < 26; ++i) {
            if (countS[i] > countT[i]) {
                steps += countS[i] - countT[i];
            }
        }
        return steps;
    }
};
      

class Solution {
    public int minSteps(String s, String t) {
        int[] countS = new int[26];
        int[] countT = new int[26];
        for (char c : s.toCharArray()) countS[c - 'a']++;
        for (char c : t.toCharArray()) countT[c - 'a']++;
        int steps = 0;
        for (int i = 0; i < 26; i++) {
            if (countS[i] > countT[i]) {
                steps += countS[i] - countT[i];
            }
        }
        return steps;
    }
}
      

var minSteps = function(s, t) {
    let countS = new Array(26).fill(0);
    let countT = new Array(26).fill(0);
    for (let c of s) countS[c.charCodeAt(0) - 97]++;
    for (let c of t) countT[c.charCodeAt(0) - 97]++;
    let steps = 0;
    for (let i = 0; i < 26; i++) {
        if (countS[i] > countT[i]) {
            steps += countS[i] - countT[i];
        }
    }
    return steps;
};