Minimum Number of Steps to Make Two Strings Anagram II Solution
Minimum Number of Steps to Make Two Strings Anagram II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Steps to Make Two Strings Anagram II is a medium coding problem on strings, hash table and counting, asked in Amazon, Google and Infosys interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Google, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
In one step you may append any character to the end of s or of t.
Return the minimum number of steps needed to make s and t anagrams of each other — same letters with the same multiplicities, in any order.
Example 1
Input: s = "codekairo", t = "kairo"
Output: 4
Explanation: `t` is missing one each of `c`, `o`, `d` and `e`.
Example 2
Input: s = "night", t = "thing"
Output: 0
Explanation: Already anagrams.
Example 3
Input: s = "leetcode", t = "coats"
Output: 7
Explanation: `t` needs `d` and three `e`s and an `l`; `s` needs `a` and `s`.
Constraints
1 <= s.length, t.length <= 2 * 10^5s and t consist of lowercase English letters.
Hints for Minimum Number of Steps to Make Two Strings Anagram II
Hint 1
Characters can only be added, never removed — so neither string can lose a surplus.
Hint 2
For each letter, the string with fewer copies must be topped up to match the other.
Hint 3
Sum the absolute differences of the 26 letter counts.
How to solve Minimum Number of Steps to Make Two Strings Anagram II
Tally both strings. For each letter, the one with fewer occurrences needs the difference appended, so the answer is the sum of |count_s[c] - count_t[c]| over the alphabet.
Approach
- Count the 26 letters in
sand int. - Add up the absolute differences.
Why it works
Because appends are the only operation, a surplus on either side is permanent — it must be matched rather than removed. The letters are independent, so the total is simply the sum of per-letter shortfalls in both directions, which the absolute value captures in one term.
Complexity
- Time —
O(n + m) - Space —
O(1) — two 26-slot tallies
Pitfalls
- Both directions count:
smay need characters too, not onlyt. - The absolute difference — not the maximum count, and not half the difference.
- Characters cannot be deleted, so the lengths need not end up equal to either original.
Reference solution
Python
def minSteps(s: str, t: str) -> int:
a = [0] * 26
b = [0] * 26
for c in s:
a[ord(c) - 97] += 1
for c in t:
b[ord(c) - 97] += 1
return sum(abs(a[i] - b[i]) for i in range(26))Java
public static int minSteps(String s, String t) {
int[] a = new int[26];
int[] b = new int[26];
for (int i = 0; i < s.length(); i++) a[s.charAt(i) - 'a']++;
for (int i = 0; i < t.length(); i++) b[t.charAt(i) - 'a']++;
int steps = 0;
for (int i = 0; i < 26; i++) steps += Math.abs(a[i] - b[i]);
return steps;
}C++
int minSteps(string s, string t) {
vector<int> a(26, 0), b(26, 0);
for (char c : s) a[c - 'a']++;
for (char c : t) b[c - 'a']++;
int steps = 0;
for (int i = 0; i < 26; i++) steps += abs(a[i] - b[i]);
return steps;
}JavaScript
var minSteps = function(s, t) {
var a = [], b = [], i;
for (i = 0; i < 26; i++) { a.push(0); b.push(0); }
for (i = 0; i < s.length; i++) a[s.charCodeAt(i) - 97]++;
for (i = 0; i < t.length; i++) b[t.charCodeAt(i) - 97]++;
var steps = 0;
for (i = 0; i < 26; i++) steps += Math.abs(a[i] - b[i]);
return steps;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets