Show problems as
Classic problem #1347MediumHash TableStringCounting

Minimum Number of Steps to Make Two Strings Anagram

Real-world version: Restamps To Match The Tray
Tracked in this browser only
Read Minimum Number of Steps to Make Two Strings Anagram on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A ceramics studio keeps two trays with the same number of tiles. The trays arrive as strings target and tray of equal length, and each character is the lowercase letter stamped on one tile.

You may take any tile out of tray and restamp it with any lowercase letter you like. One restamp changes one tile, and a restamped tile stays in tray.

Return the fewest restamps that leave tray holding exactly the same tally of every letter as target. Where the tiles sit inside a tray never matters, only how many of each letter it holds.

Examples

Example 1

Input
target = "kite", tray = "kits"
Output
1

Both trays hold one `k`, one `i` and one `t`. The `s` in `tray` has no counterpart, so restamping it as `e` gives the tallies of `target`.

Example 2

Input
target = "sunny", tray = "runny"
Output
1

The `u`, both `n`s and the `y` already line up in tally. Restamping the `r` as `s` finishes the job.

Example 3

Input
target = "wolf", tray = "flow"
Output
0

Each of `w`, `o`, `l` and `f` appears once in both trays, so no restamp is needed even though the tiles sit in a different order.

Example 4

Input
target = "zzzz", tray = "zabc"
Output
3

`target` needs four `z` tiles and `tray` has one, so the `a`, `b` and `c` all get restamped as `z`.

Example 5

Input
target = "moon", tray = "noon"
Output
1

`tray` holds two `n` tiles where `target` holds one, and holds no `m` where `target` holds one, so restamping one `n` as `m` is enough.

Constraints

  • 1 <= target.length <= 5 * 10^4
  • target.length == tray.length
  • target and tray consist of lowercase English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_steps(target: str, tray: str) -> int:
Java
public int minSteps(String target, String tray)

More on the same topics