Skip to main content
Talentd

Minimum Number of Steps to Make Two Strings Anagram II - Solution & Explanation

MediumHash TableStringCounting11 min readAsked at: Wealthfront
Practice this problem

Problem Statement

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 * 105
  • s and t consist of lowercase English letters.

Approach Overview

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 1: Character Frequency Count

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Hash Table for Frequency Count

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Character Frequency Count

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.

Hash Table for Frequency Count

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 CountO(n)O(k)Useful when characters may extend beyond a fixed alphabet or when writing more generic solutions.

Video Solution

Minimum Number of Steps to Make Two Strings Anagram II | LeetCode 2186 | LeetCode Weekly Contest 282 • Bro Coders • 1,345 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Minimum Number of Steps to Make Two Strings Anagram II easy or hard?
This problem is classified as Medium on LeetCode but conceptually straightforward once you recognize it as a frequency counting task. The main challenge is identifying that the number of deletions equals the total difference between character counts in the two strings.
Minimum Number of Steps to Make Two Strings Anagram II Python/Java solution
Most Python solutions use a list of size 26 or collections.Counter to track character frequencies. Java solutions typically use an int[26] array or a HashMap<Character, Integer>. Both implementations iterate through the strings and sum absolute frequency differences to compute the answer.
How to solve Minimum Number of Steps to Make Two Strings Anagram II in O(n)?
Use a frequency counter. Increment counts for each character in the first string and decrement for each character in the second string. After processing both strings, sum the absolute values of the remaining frequency differences. Each difference represents a character that must be deleted.
What is the best approach for Minimum Number of Steps to Make Two Strings Anagram II?
The best approach uses a character frequency count with a fixed array of size 26. Count characters in the first string, subtract counts using the second string, then sum the absolute differences. This runs in O(n) time with O(1) space and is typically the expected interview solution.
Is Minimum Number of Steps to Make Two Strings Anagram II asked at Google/Amazon/Meta?
Anagram and frequency-count problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations involving character counting, hash maps, and string manipulation are common in coding rounds because they test algorithmic fundamentals and data structure knowledge.
What data structure is used in Minimum Number of Steps to Make Two Strings Anagram II?
The primary data structure is a frequency counter implemented using either an integer array or a hash table. The array approach stores counts for each letter, while the hash table version dynamically tracks character frequencies with constant-time lookups.
What is the time complexity of Minimum Number of Steps to Make Two Strings Anagram II?
The optimal solution runs in O(n) time where n is the combined length of both strings. Each string is scanned once to update frequency counts, and a constant-size array or hash map is processed afterward. Space complexity is O(1) with a fixed alphabet array or O(k) with a hash map.

Ready to solve this problem?

Practice Minimum Number of Steps to Make Two Strings Anagram II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Steps to Make Two Strings Anagram