Minimum Number of Steps to Make Two Strings Anagram - Solution & Explanation
Problem Statement
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.lengthsandtconsist of lowercase English letters only.
Approach Overview
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 1: Frequency Count Method
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.
Complexity
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 2: Counting
We can use a hash table or an array cnt to count the occurrences of each character in the string s. Then, we traverse the string t. For each character, we decrement its count in cnt. If the decremented value is less than 0, it means that this character appears more times in the string t than in the string s. In this case, we need to replace this character and increment the answer by one.
After the traversal, we return the answer.
The time complexity is O(m + n), and the space complexity is O(|\Sigma|), where m and n are the lengths of the strings s and t, respectively, and |\Sigma| is the size of the character set. In this problem, the character set consists of lowercase letters, so |\Sigma| = 26.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Frequency Count Method | Time Complexity: O(n), where n is the length of the strings (since they are of equal length). |
| Counting | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Leetcode 1347. Minimum Number of Steps to Make Two Strings Anagram • Fraz • 11,225 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Number of Steps to Make Two Strings Anagram easy or hard?
Minimum Number of Steps to Make Two Strings Anagram Python/Java solution
How to solve Minimum Number of Steps to Make Two Strings Anagram in O(n)?
What is the best approach for Minimum Number of Steps to Make Two Strings Anagram?
Is Minimum Number of Steps to Make Two Strings Anagram asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Steps to Make Two Strings Anagram?
What is the time complexity of Minimum Number of Steps to Make Two Strings Anagram?
Ready to solve this problem?
Practice Minimum Number of Steps to Make Two Strings Anagram with our built-in code editor and test cases.
Practice on FleetCode