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 Table String

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 * 10⁵
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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int minSteps(String s, String t) {6        Map<Character, Integer> sCounts = new HashMap<>();7        for (char c : s.toCharArray()) {8            sCounts.put(c, sCounts.getOrDefault(c, 0) + 1);9        }10 11        Map<Character, Integer> tCounts = new HashMap<>();12        for (char c : t.toCharArray()) {13            tCounts.put(c, tCounts.getOrDefault(c, 0) + 1);14        }15 16        int steps = 0;17        for (char c = 'a'; c <= 'z'; c++) {18            int sCount = sCounts.getOrDefault(c, 0);19            int tCount = tCounts.getOrDefault(c, 0);20            steps += Math.abs(sCount - tCount);21        }22 23        return steps;24    }25}

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.

A more efficient approach utilizes a single integer array of size 26 to track the net difference in character frequencies between the two strings. We first iterate through string s, incrementing the count for each character in the array. Then, we iterate through string t, decrementing the count for each character. After processing both strings, each element count[i] in the array represents the difference in frequency for the character 'a' + i. The total number of steps is the sum of the absolute values of all elements in this array.

Algorithm

Initialize an integer array counts of size 26 with all elements set to 0. This array will store the net frequency difference for each character.
Iterate through each character c in string s. For each character, increment the corresponding counter in the array: counts[c - 'a']++.
Iterate through each character c in string t. For each character, decrement the corresponding counter in the array: counts[c - 'a']--.
After these two loops, counts[i] holds the value (frequency of 'a'+i in s) - (frequency of 'a'+i in t).
Initialize a variable steps to 0.
Iterate through the counts array. For each element count, add its absolute value to steps.
Return steps.

Walkthrough

Since the input strings are guaranteed to contain only lowercase English letters, we can use a simple array of size 26 as a frequency map instead of a HashMap. This is more performant due to direct memory access and avoids the overhead of hashing.

The core idea is to use a single array to represent the difference in character counts. We populate the array with counts from s and then subtract the counts from t. The final values in the array represent count_s[char] - count_t[char]. The total number of characters to be added is the sum of the absolute values of these differences.

1class Solution {2    public int minSteps(String s, String t) {3        int[] counts = new int[26];4        5        // Increment for characters in s6        for (char c : s.toCharArray()) {7            counts[c - 'a']++;8        }9        10        // Decrement for characters in t11        for (char c : t.toCharArray()) {12            counts[c - 'a']--;13        }14        15        int steps = 0;16        // Sum the absolute differences17        for (int count : counts) {18            steps += Math.abs(count);19        }20        21        return steps;22    }23}

For example, if counts[0] (for character 'a') is 2, it means s has two more 'a's than t, so we need to add two 'a's to t. If counts[0] is -3, t has three more 'a's, so we need to add three 'a's to s. In both cases, the number of steps for 'a' is abs(counts[0]).

Complexity

Time

O(N + M), where N is the length of `s` and M is the length of `t`. We perform a single pass over each string and one pass over the 26-element frequency array. This is the most efficient time complexity possible as we must look at every character at least once.

Space

O(1). We use a single integer array of a fixed size (26), which is constant space and does not depend on the input string lengths.

Trade-offs

Pros

Highly efficient in both time and space due to direct array indexing and no object overhead.
Uses a single, compact data structure, making the code concise and fast.
Optimal solution for the given constraints.

Cons

This approach is specifically tailored to a known, small character set (lowercase English letters). It would need modification for larger character sets like Unicode.

Solutions

Solution

1class Solution {2public3  int minSteps(String s, String t) {4    int[] cnt = new int[26];5    for (char c : s.toCharArray()) {6      ++cnt[c - 'a'];7    }8    for (char c : t.toCharArray()) {9      --cnt[c - 'a'];10    }11    int ans = 0;12    for (int v : cnt) {13      ans += Math.abs(v);14    }15    return ans;16  }17}

1/** * @param {string} s * @param {string} t * @return {number} */ var minSteps =2  function (s, t) {3    let cnt = new Array(26).fill(0);4    for (const c of s) {5      ++cnt[c.charCodeAt() - " a ".charCodeAt()];6    }7    for (const c of t) {8      --cnt[c.charCodeAt() - " a ".charCodeAt()];9    }10    let ans = 0;11    for (const v of cnt) {12      ans += Math.abs(v);13    }14    return ans;15  };

1class Solution {2public:3  int minSteps(string s, string t) {4    vector<int> cnt(26);5    for (char &c : s)6      ++cnt[c - 'a'];7    for (char &c : t)8      --cnt[c - 'a'];9    int ans = 0;10    for (int &v : cnt)11      ans += abs(v);12    return ans;13  }14};

1class Solution:2    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())

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 problem