Get started

Minimum Number of Steps to Make Two Strings Anagram II — Medium Problem & Solution

In one step you may append any character to the end of s or of t.

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

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))

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue