Watch 8 video solutions for Minimum Number of Steps to Make Two Strings Anagram II, a medium level problem involving Hash Table, String, Counting. This walkthrough by Bro Coders has 1,338 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |