Problem Description

You are given two strings s and t that have the same length. Your goal is to transform string t into an anagram of string s by replacing characters in t.

In each step, you can:

• Choose any character in string t
• Replace it with any other character

An anagram is a rearrangement of letters - two strings are anagrams if they contain exactly the same characters with the same frequencies, just potentially in a different order. For example, "listen" and "silent" are anagrams.

The task is to find the minimum number of steps (character replacements) needed to make t an anagram of s.

For example:

• If s = "bab" and t = "aba", they are already anagrams, so the answer is 0
• If s = "leetcode" and t = "practice", you would need to replace several characters in t to match the character frequencies in s

The key insight is that you need to make the character frequencies in t match those in s. If s has more of a certain character than t, you'll need to add that character to t by replacing other characters. The minimum number of replacements equals the number of excess characters in t that don't match with s.

Intuition

To make t an anagram of s, we need the character frequencies in both strings to be identical. Let's think about what this means:

If s has 3 'a's and t has 5 'a's, then t has 2 extra 'a's that need to be replaced with other characters. Conversely, if s has 5 'a's and t has only 3 'a's, then t is missing 2 'a's, which means we need to replace 2 other characters in t to become 'a's.

The key realization is that we only need to count the excess characters in t. Why? Because:

• For every character that appears more frequently in t than in s, we have excess characters that must be replaced
• For every character that appears less frequently in t than in s, there's a deficit that will be filled by replacing those excess characters

Since each replacement fixes both an excess (removing an unwanted character) and a deficit (adding a needed character), the minimum number of replacements equals the total number of excess characters in t.

Here's the clever part of the solution: We start by counting all characters in s. Then, as we traverse t, we decrement the count for each character we encounter. When a count goes negative, it means we've seen this character more times in t than it exists in s - this is an excess character that needs replacement. By counting how many times we go negative, we get the exact number of replacements needed.

For example, if s = "aab" and t = "bba":

• Count in s: {'a': 2, 'b': 1}
• Processing t:
  • First 'b': count becomes {'a': 2, 'b': 0}
  • Second 'b': count becomes {'a': 2, 'b': -1} (excess found, increment answer)
  • 'a': count becomes {'a': 1, 'b': -1}
• Result: 1 replacement needed

Solution Approach

The solution uses a counting approach with a hash table to track character frequencies.

Step 1: Count characters in string s

We use Python's Counter from the collections module to create a hash table cnt that stores the frequency of each character in string s. For example, if s = "leetcode", then cnt would be {'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}.

Step 2: Process string t and count excess characters

We traverse through each character c in string t and perform two operations:

1. Decrement the count of character c in our hash table: cnt[c] -= 1
2. Check if the count becomes negative: cnt[c] < 0

When cnt[c] becomes negative, it indicates that character c appears more times in t than in s. This is an excess character that needs to be replaced.

Step 3: Track the number of replacements

We maintain a variable ans to count the total number of excess characters. Each time we encounter a negative count (meaning we found an excess character), we increment ans by 1.

Implementation walkthrough:

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        cnt = Counter(s)  # Count frequency of each character in s
        ans = 0           # Initialize replacement counter
        for c in t:       # Process each character in t
            cnt[c] -= 1   # Decrement the count for this character
            ans += cnt[c] < 0  # If count is negative, increment answer
        return ans

The expression ans += cnt[c] < 0 is a clever Python idiom where cnt[c] < 0 evaluates to True (which equals 1) when the count is negative, or False (which equals 0) otherwise.

Time Complexity: O(n) where n is the length of the strings, as we traverse both strings once.

Space Complexity: O(k) where k is the number of unique characters in string s, typically O(26) for lowercase English letters, which is effectively O(1).

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example: s = "anagram" and t = "mangaar"

Step 1: Count characters in string s

First, we create a frequency map of characters in s:

• s = "anagram" → cnt = {'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1}

Step 2: Process each character in t and track excess

Now we traverse t = "mangaar" character by character:

Result: All counts reach exactly 0, meaning t already contains the exact same characters as s. Therefore, ans = 0 - no replacements needed! Indeed, "mangaar" is already an anagram of "anagram".

Let's try another example where replacements ARE needed:

s = "abc" and t = "bba"

Step 1: Count characters in s:

• cnt = {'a': 1, 'b': 1, 'c': 1}

Step 2: Process t = "bba":

Result: ans = 1

This makes sense! String t has an extra 'b' (2 'b's vs 1 in s) and is missing a 'c'. We need exactly 1 replacement: change one 'b' to 'c' to get "bca" or "abc", both anagrams of "abc".

Solution Implementation

Time and Space Complexity

The time complexity is O(m + n), where m is the length of string s and n is the length of string t. This is because:

• Creating the Counter for string s takes O(m) time as it needs to iterate through all characters in s
• The for loop iterates through all characters in string t, which takes O(n) time
• Each operation inside the loop (dictionary access, decrement, comparison) takes O(1) time

The space complexity is O(|Σ|), where |Σ| represents the size of the character set. In this problem, since we're dealing with lowercase letters, |Σ| = 26. The Counter object stores at most 26 unique characters (all lowercase letters), so the space used is bounded by the alphabet size rather than the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Problem - Counting Both Deficits and Excesses

The Mistake: A common error is trying to count both the characters that are missing from t (deficit) AND the characters that are excess in t, then taking some combination of these counts. For example:

# INCORRECT approach
def minSteps(self, s: str, t: str) -> int:
    cnt_s = Counter(s)
    cnt_t = Counter(t)
  
    missing = 0  # Characters in s but not enough in t
    excess = 0   # Characters in t but not enough in s
  
    for char in cnt_s:
        if cnt_s[char] > cnt_t.get(char, 0):
            missing += cnt_s[char] - cnt_t.get(char, 0)
  
    for char in cnt_t:
        if cnt_t[char] > cnt_s.get(char, 0):
            excess += cnt_t[char] - cnt_s.get(char, 0)
  
    return max(missing, excess)  # Or return (missing + excess) // 2

Why This is Wrong: The number of missing characters always equals the number of excess characters. If s needs 3 more 'a's than t has, then t must have 3 excess characters of other types. Counting both leads to redundant work and potential confusion.

The Correct Insight: You only need to count EITHER the excess characters in t OR the deficit characters in t. Both will give the same answer. The provided solution elegantly counts only the excess characters.

Pitfall 2: Using Wrong Default Value for Counter

The Mistake:

# INCORRECT - will cause KeyError
def minSteps(self, s: str, t: str) -> int:
    cnt = {}  # Using regular dict instead of Counter
    for c in s:
        cnt[c] = cnt.get(c, 0) + 1
  
    ans = 0
    for c in t:
        cnt[c] -= 1  # KeyError if c not in cnt!
        if cnt[c] < 0:
            ans += 1
    return ans

Why This is Wrong: If character c from string t doesn't exist in string s, a regular dictionary will throw a KeyError when trying to decrement. Counter automatically handles missing keys by treating them as having a value of 0.

The Solution: Either use Counter (which handles missing keys gracefully) or manually check for key existence:

# Option 1: Use Counter (recommended)
cnt = Counter(s)

# Option 2: Manual checking with regular dict
for c in t:
    cnt[c] = cnt.get(c, 0) - 1
    if cnt[c] < 0:
        ans += 1

Pitfall 3: Overthinking with Sorting or Complex Matching

The Mistake:

# INCORRECT - Unnecessarily complex
def minSteps(self, s: str, t: str) -> int:
    s_sorted = sorted(s)
    t_sorted = sorted(t)
  
    changes = 0
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if s_sorted[i] == t_sorted[j]:
            i += 1
            j += 1
        elif s_sorted[i] < t_sorted[j]:
            changes += 1
            i += 1
        else:
            j += 1
  
    return changes + (len(s) - i)

Why This is Wrong: Sorting and trying to match characters position-by-position doesn't correctly count the minimum replacements needed. This approach fails because it doesn't properly track character frequencies and can miss valid matches.

The Solution: Stick to frequency counting. The problem is fundamentally about matching character frequencies, not about matching positions or finding a specific arrangement.