You are given two strings s and t. In one step, you can append any character to either s or t.
Return the minimum number of steps to make s and t anagrams of each other.
An anagram of a string is a string that contains the same characters with a different (or the same) ordering.
Example 1:
Input: s = "leetcode", t = "coats" Output: 7 Explanation: - In 2 steps, we can append the letters in "as" onto s = "leetcode", forming s = "leetcodeas". - In 5 steps, we can append the letters in "leede" onto t = "coats", forming t = "coatsleede". "leetcodeas" and "coatsleede" are now anagrams of each other. We used a total of 2 + 5 = 7 steps. It can be shown that there is no way to make them anagrams of each other with less than 7 steps.
Example 2:
Input: s = "night", t = "thing" Output: 0 Explanation: The given strings are already anagrams of each other. Thus, we do not need any further steps.
Constraints:
1 <= s.length, t.length <= 2 * 105s and t consist of lowercase English letters.Problem Overview: You receive two strings s and t. The goal is to remove the minimum number of characters so both strings become anagrams of each other. Two strings are anagrams when they contain the same characters with the same frequencies, regardless of order.
Approach 1: Character Frequency Count (O(n) time, O(1) space)
This approach uses a fixed-size frequency array for lowercase English characters. Iterate through string s and increment counts for each character. Then iterate through t and decrement the corresponding counts. The array now represents the net difference in frequency between both strings. The total number of deletions required equals the sum of absolute values of all frequency differences. Because the alphabet size is constant (26 letters), the extra memory remains constant. This approach is fast, cache-friendly, and typically preferred when the character set is known and small.
Approach 2: Hash Table for Frequency Count (O(n) time, O(k) space)
This version uses a hash map instead of a fixed array. Traverse string s and store character counts in a hash table. Then iterate through t, decrementing counts for matching characters. After processing both strings, iterate over the map and sum the absolute values of all stored counts. Each remaining difference represents characters that must be removed. This method is more flexible when the character set is larger or unknown. It directly leverages a hash table to track frequencies while performing constant-time lookups.
Both approaches rely on the same insight: anagrams require identical character counts. Any imbalance between the two strings must be removed. Instead of simulating deletions directly, you compute the difference in frequencies and sum those mismatches.
The core operations involve iterating through characters and updating counters, which makes this a classic string processing problem combined with counting techniques. The algorithm scales linearly with the combined length of the two strings.
Recommended for interviews: The character frequency array is usually the expected solution. It runs in linear time O(n) and constant space O(1), making it both optimal and simple to implement. Demonstrating the hash table approach first can show general problem-solving thinking, but the fixed array solution signals strong awareness of constraints and optimization.
To make two strings anagrams, the difference in the frequency of each character in the strings must be adjusted by appending characters. By counting the frequency of each character in both strings, we can calculate the number of characters that need to be added to make the strings anagrams.
This C program uses two arrays to keep track of character frequencies in the input strings s and t. By iterating through these arrays, it calculates the number of differing characters between the two strings and returns the total number of steps needed to make the strings anagrams by appending characters.
Time Complexity: O(n + m), where n and m are the lengths of strings s and t respectively.
Space Complexity: O(1), as the frequency count arrays have a fixed size of 26.
Instead of fixed-size arrays, we can use hash tables (like dictionaries in Python or HashMaps in Java) to dynamically account for character frequencies, which might be more efficient in some scenarios if we're dealing with a more diverse character set, although in this specific problem, it's less necessary than fixed arrays.
This function leverages Python's collections.Counter to compute character frequencies dynamically, then calculates the minimum steps to make the strings anagrams by iterating over the union of unique characters in the strings.
Time Complexity: O(n + m), where n and m are the number of characters in s and t respectively.
Space Complexity: O(1), considering only the lowercase English alphabet. The hash table solution is generally O(k), where k is the character set size.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Character Frequency Count | Time Complexity: O(n + m), where n and m are the lengths of strings |
| Hash Table for Frequency Count | Time Complexity: O(n + m), where n and m are the number of characters in |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Frequency Count (Array) | O(n) | O(1) | Best when the character set is fixed (e.g., lowercase English letters). Most optimal and common interview solution. |
| Hash Table for Frequency Count | O(n) | O(k) | Useful when characters may extend beyond a fixed alphabet or when writing more generic solutions. |
Minimum Number of Steps to Make Two Strings Anagram II | LeetCode 2186 | LeetCode Weekly Contest 282 • Bro Coders • 1,338 views views
Watch 7 more video solutions →Practice Minimum Number of Steps to Make Two Strings Anagram II with our built-in code editor and test cases.
Practice on FleetCode