Scale Engineer

Minimum Number of Steps to Make Two Strings Anagram II

Med
#1991Time: O(N + M), where N is the length of `s` and M is the length of `t`. We iterate through both strings once to build the maps (O(N + M)) and then iterate a constant number of times (26) to compare frequencies. Thus, the overall complexity is dominated by the string traversals.Space: O(K), where K is the number of unique characters in the alphabet. Since the problem specifies lowercase English letters, K is at most 26, making the space complexity constant, O(1).1 company
Patterns
Counting
Data structures
Hash TableString
Companies
Wealthfront

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses two HashMaps to store the character frequencies for each string, s and t. We first iterate through both strings to populate their respective frequency maps. Then, we iterate through all possible lowercase English letters ('a' through 'z') and for each letter, we find the counts from both maps (defaulting to 0 if not present). The absolute difference between these counts represents the number of appends needed for that specific character. Summing these differences for all 26 letters gives the total minimum steps required.

Algorithm

  • Initialize two HashMaps, sCounts and tCounts, to store character frequencies for strings s and t respectively.
  • Iterate through string s. For each character, increment its count in sCounts.
  • Iterate through string t. For each character, increment its count in tCounts.
  • Initialize a variable steps to 0.
  • Loop through all 26 lowercase English letters from 'a' to 'z'.
  • For each letter, get its frequency from sCounts and tCounts, using 0 as a default if the letter is not present.
  • Calculate the absolute difference between the two frequencies and add it to steps.
  • After checking all letters, steps will hold the total minimum number of appends required. Return steps.

Walkthrough

To make two strings anagrams, they must have the exact same character counts. The goal is to find the minimum number of appends to achieve this. This can be found by calculating the total number of characters that are mismatched between the two strings.

This method uses HashMaps, a common data structure for frequency counting, which maps each character to its count.

import java.util.HashMap;import java.util.Map; class Solution {    public int minSteps(String s, String t) {        Map<Character, Integer> sCounts = new HashMap<>();        for (char c : s.toCharArray()) {            sCounts.put(c, sCounts.getOrDefault(c, 0) + 1);        }         Map<Character, Integer> tCounts = new HashMap<>();        for (char c : t.toCharArray()) {            tCounts.put(c, tCounts.getOrDefault(c, 0) + 1);        }         int steps = 0;        for (char c = 'a'; c <= 'z'; c++) {            int sCount = sCounts.getOrDefault(c, 0);            int tCount = tCounts.getOrDefault(c, 0);            steps += Math.abs(sCount - tCount);        }         return steps;    }}

For any character c, if s has more c's than t, we need to append sCount - tCount copies of c to t. Conversely, if t has more, we need to append tCount - sCount copies to s. In both cases, the number of appends for character c is abs(sCount - tCount). Summing this over all characters gives the total steps.

Complexity

Time

O(N + M), where N is the length of `s` and M is the length of `t`. We iterate through both strings once to build the maps (O(N + M)) and then iterate a constant number of times (26) to compare frequencies. Thus, the overall complexity is dominated by the string traversals.

Space

O(K), where K is the number of unique characters in the alphabet. Since the problem specifies lowercase English letters, K is at most 26, making the space complexity constant, O(1).

Trade-offs

Pros

  • Conceptually straightforward and easy to implement.

  • Flexible and general; it would work for any character set, not just lowercase English letters.

Cons

  • Slightly less performant due to the overhead of hashing and Map.Entry object creation.

  • Uses more memory in practice compared to a simple array.

Solutions

class Solution {public  int minSteps(String s, String t) {    int[] cnt = new int[26];    for (char c : s.toCharArray()) {      ++cnt[c - 'a'];    }    for (char c : t.toCharArray()) {      --cnt[c - 'a'];    }    int ans = 0;    for (int v : cnt) {      ans += Math.abs(v);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem