#2186

Medium

LeetCode Problem Workspace

Minimum Number of Steps to Make Two Strings Anagram II

Compute the fewest character insertions needed to turn two strings into anagrams using hash table frequency counts efficiently.

hash table string counting

Problem Statement

Given two strings s and t, you can append any character to either string in one step. Compute the minimum steps needed to make s and t anagrams of each other.

An anagram consists of the same characters in any order. Return the total steps required to align both strings character counts, ensuring the resulting strings are anagrams.

Examples

Example 1

Input: s = "leetcode", t = "coats"

Output: 7

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

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.

Solution Approach

Use frequency maps

Create two hash tables to store character counts for s and t. For each character in the English alphabet, compute the difference between the counts in both strings. This difference represents the number of insertions needed for that character.

Sum absolute differences

Iterate through all characters in the hash tables and sum the absolute differences in counts. This total gives the minimum number of steps required to balance the characters between the strings and form anagrams.

Optimize with a single pass

Instead of separate maps, increment counts for s and decrement for t in a single hash table. Then sum positive values in the table to find the required steps. This reduces space usage and improves runtime by avoiding two full traversals.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m) where n and m are the lengths of s and t, as we traverse both strings once and iterate over at most 26 characters. Space complexity is O(1) because the hash table only stores counts for lowercase letters, a fixed size of 26.

What Interviewers Usually Probe

Counts mismatch between s and t indicates hash table usage.
Ask for O(n) approach rather than sorting the strings.
Check handling of strings already anagrams, expecting zero steps.

Common Pitfalls or Variants

Common pitfalls

Forgetting to take absolute differences, causing negative step counts.
Using sorting instead of counting, which increases time complexity unnecessarily.
Not accounting for characters missing in one string, leading to undercounted steps.

Follow-up variants

Instead of appending, compute deletions to achieve anagrams.
Allow only one string to be modified to match the other as an anagram.
Extend to Unicode characters instead of just lowercase English letters.

FAQ

What is the minimum number of steps to make two strings anagrams II problem about?

It asks how many single-character insertions are needed to make two strings anagrams by matching their character counts.

Which pattern does this problem follow?

It follows the Hash Table plus String pattern, emphasizing character frequency counting.

Can this be solved without hash tables?

Yes, but alternatives like sorting increase time complexity and reduce efficiency for large strings.

What should I do if the strings are already anagrams?

Return 0 steps since no insertions are needed when character counts already match.

How does GhostInterview handle large strings?

It efficiently uses a fixed-size hash table for lowercase letters, keeping operations linear even for very long strings.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        cnt = Counter(s)
        for c in t:
            cnt[c] -= 1
        return sum(abs(v) for v in cnt.values())

Continue Practicing

#2182 construct string with repeat limit #2131 longest palindrome by concatenating two letter words #2283 check if number has equal digit count and digit value