Watch 10 video solutions for Minimum Number of Steps to Make Two Strings Anagram, a medium level problem involving Hash Table, String, Counting. This walkthrough by Fraz has 11,217 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.
Return the minimum number of steps to make t an anagram of s.
An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.
Example 1:
Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.
Example 2:
Input: s = "leetcode", t = "practice" Output: 5 Explanation: 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 Explanation: "anagram" and "mangaar" are anagrams.
Constraints:
1 <= s.length <= 5 * 104s.length == t.lengths and t consist of lowercase English letters only.Problem Overview: You are given two strings s and t of the same length. In one step you can replace any character in t. The goal is to compute the minimum number of replacements required so that t becomes an anagram of s.
Approach 1: Sorting and Compare (O(n log n) time, O(n) space)
A straightforward way to reason about anagrams is sorting both strings. If two strings are anagrams, their sorted versions are identical. Sort s and t, then iterate through both arrays and count mismatched characters. Each mismatch indicates a character in t that must be replaced. Sorting dominates the runtime at O(n log n), while storing sorted arrays requires O(n) space. This approach works but wastes time doing full ordering when the problem only requires frequency comparison.
Approach 2: Frequency Count Method (O(n) time, O(1) space)
The optimal solution relies on counting character frequencies using a fixed-size array or hash map. Iterate through string s and increment counts for each character. Then iterate through t and decrement the corresponding counts. If a count becomes negative, it means t has more of that character than s, so a replacement is required. Increment the step counter in that case. Because the alphabet size is constant (26 lowercase letters), the frequency structure uses constant space. The entire algorithm runs in O(n) time with O(1) space.
This technique is common in problems involving anagrams or character balancing. The idea is to track the difference between character distributions rather than reconstructing the actual anagram. A simple integer array indexed by char - 'a' works well, though a hash table also works if the character set is larger.
Conceptually, you are computing how many characters in t exceed the available counts from s. Every extra occurrence forces a replacement. This makes the solution a classic counting pattern combined with efficient string traversal.
Recommended for interviews: The frequency count method. Interviewers expect you to recognize that anagrams depend only on character counts, not order. Mentioning a sorting approach first demonstrates baseline reasoning, but moving to the O(n) counting solution shows stronger algorithmic intuition and understanding of constant-space optimizations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting Both Strings | O(n log n) | O(n) | Simple conceptual solution when constraints are small or when sorting utilities are already used. |
| Frequency Count (Hash Table / Array) | O(n) | O(1) | Optimal approach for large strings. Best for interview settings and production code. |