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.
In this method, we need to count the frequency of each character in strings s and t. We then calculate the number of changes required in t by comparing these frequencies. Specifically, for each character, if the frequency count in s is greater than in t, those are the extra characters needed in t. The total number of these extra characters across all characters gives the result.
This C code defines a function that calculates the difference in frequency of each character between the two strings. It uses an array of size 26 to store the frequency count of characters. The function iterates through the string s to increment the frequency and then through t to decrement. The remaining positive values in the array represent the total change needed.
Time Complexity: O(n), where n is the length of the strings (since they are of equal length).
Space Complexity: O(1), since the space required does not depend on the input size.
| 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. |
Leetcode 1347. Minimum Number of Steps to Make Two Strings Anagram • Fraz • 11,217 views views
Watch 9 more video solutions →Practice Minimum Number of Steps to Make Two Strings Anagram with our built-in code editor and test cases.
Practice on FleetCode