Minimum Number of Steps to Make Two Strings Anagram II

Medium
1031.

Minimum Number of Steps to Make Two Strings Anagram II

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.

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^5
  • s and t consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var minSteps = function(s, t) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Minimum Number of Steps to Make Two Strings Anagram II

  1. Hint 1

    Characters can only be added, never removed — so neither string can lose a surplus.

  2. Hint 2

    For each letter, the string with fewer copies must be topped up to match the other.

  3. 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

  1. Count the 26 letters in s and in t.
  2. 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: s may need characters too, not only t.
  • 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