#1347

Medium

LeetCode Problem Workspace

Minimum Number of Steps to Make Two Strings Anagram

Calculate the minimum steps to transform one string into an anagram of another using character replacements efficiently.

hash table string counting

Problem Statement

Given two strings s and t of the same length, you can replace any character in t with another lowercase letter in one step. Your task is to determine the minimum number of such steps required to make t an anagram of s, where an anagram contains exactly the same letters in any order.

Implement a solution that efficiently counts character differences using a hash table. The strings consist only of lowercase English letters and may be up to 50,000 characters long, so a linear-time approach is required to avoid performance issues.

Examples

Example 1

Input: s = "bab", t = "aba"

Output: 1

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

Example 2

Input: s = "leetcode", t = "practice"

Output: 5

Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s.

Example 3

Input: s = "anagram", t = "mangaar"

Output: 0

"anagram" and "mangaar" are anagrams.

Constraints

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

Solution Approach

Count character frequencies

Build a hash table for each string to count the occurrences of each lowercase letter. This allows precise tracking of which characters in t exceed or lack the counts needed to match s.

Calculate required replacements

Iterate through the hash table differences. For each character where t has more than s, accumulate the surplus. The sum of all positive surpluses directly gives the minimum replacement steps to form an anagram.

Optimize for constant space

Since there are only 26 lowercase letters, use a fixed-size array instead of a dynamic hash map. This keeps space complexity O(1) and simplifies updates during the difference calculation.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N) because each string is traversed once for counting and once for calculating differences. Space complexity is O(1) since the hash table uses a fixed 26-element array regardless of input size.

What Interviewers Usually Probe

Expecting recognition of the hash table pattern for character counting.
Looking for O(N) time and O(1) space solution using frequency differences.
Check understanding of anagram definition and replacement counting logic.

Common Pitfalls or Variants

Common pitfalls

Confusing total mismatches with minimum replacement steps; only count surplus in t.
Using dynamic hash maps unnecessarily, increasing space complexity.
Forgetting that strings are guaranteed equal length, leading to off-by-one errors.

Follow-up variants

Allowing uppercase letters increases hash table size but keeps the same pattern.
Counting the minimum swaps instead of replacements introduces a different transformation metric.
Handling multiple target strings t1, t2 requires repeated application of the same frequency difference approach.

FAQ

What is the key insight for solving Minimum Number of Steps to Make Two Strings Anagram?

The key is counting the frequency of each character in both strings and summing the positive differences for characters in t.

Can this problem be solved without a hash table?

Technically yes using sorting, but a hash table provides linear-time counting and constant space, which is optimal.

Why does using a fixed-size array work for this problem?

Because only lowercase English letters exist, a 26-element array suffices to store all character counts efficiently.

How do I handle very long strings efficiently?

Use a single-pass hash table frequency count and difference calculation to maintain O(N) time without extra space.

Does GhostInterview check my solution pattern?

Yes, it verifies that your approach correctly applies the hash table plus string pattern and counts replacements accurately.

terminal

Solution

Solution 1: Counting

We can use a hash table or an array $\textit{cnt}$ to count the occurrences of each character in the string $\textit{s}$. Then, we traverse the string $\textit{t}$. For each character, we decrement its count in $\textit{cnt}$. If the decremented value is less than $0$, it means that this character appears more times in the string $\textit{t}$ than in the string $\textit{s}$. In this case, we need to replace this character and increment the answer by one.

1

2

3

4

5

6

7

8

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        cnt = Counter(s)
        ans = 0
        for c in t:
            cnt[c] -= 1
            ans += cnt[c] < 0
        return ans

Continue Practicing

#1366 rank teams by votes #1370 increasing decreasing string #1400 construct k palindrome strings