Minimum Character Replacements to Make One String an Anagram of Another

You are given two strings s and t of the same length. In one step you may pick any position in t and replace the character there with any lowercase English letter. Return the minimum number of steps needed to make t an anagram of s.

Two strings are anagrams of each other when they contain the same characters with the same multiplicities, in any order.

Function Signature

def min_steps_to_anagram(s: str, t: str) -> int:

Rules

• Only t may be changed. s stays fixed.
• Each step replaces exactly one character of t. Characters cannot be inserted or deleted, so the length of t never changes.
• The order of the characters in t never matters, because anagrams ignore order. No step is needed to rearrange characters.
• If t is already an anagram of s, the answer is 0.

Constraints

• 1 <= len(s) == len(t) <= 5 * 10^4
• s and t consist only of lowercase English letters a to z.
• The answer is at most len(t), so it fits in a 32-bit signed integer.

Examples

Example 1

Input:  s = "abc", t = "bbd"
Output: 2

Replacing the first b with a and the d with c turns t into "abc". A single replacement cannot make t an anagram of s.

Example 2

Input:  s = "night", t = "thing"
Output: 0

t already contains the same letters as s, each the same number of times.

Example 3

Input:  s = "aabbcc", t = "abcdef"
Output: 3

Replacing d, e and f with a, b and c gives "abcabc", which is an anagram of s. No sequence of two or fewer replacements works.

Fewest Character Replacements to Make an Anagram

Hints

1. Anagrams ignore order, so think about what information about each string actually decides whether two strings are anagrams.
2. Each step changes one character of t into another letter. Ask which characters of t could be left untouched.
3. The two strings have the same length, so whatever t has too much of is balanced by what it lacks.

Approach

Count how many times each of the 26 letters occurs in s and in t. For a letter c let surplus(c) = max(0, count_t(c) - count_s(c)). The answer is the sum of surplus(c) over all letters.

Lower bound: a position of t that is never replaced keeps its letter, so for every letter c at least surplus(c) of the positions of t holding c must be replaced. These position sets are disjoint across letters, so at least the sum of the surpluses is required.

Upper bound: because len(s) == len(t), the total surplus equals the total deficit (the sum over c of max(0, count_s(c) - count_t(c))). Replace each surplus character with a letter that t is still missing. After exactly sum-of-surplus steps every letter count of t matches s, and since order is irrelevant t is then an anagram of s.

The implementation keeps one array of 26 counters, adds 1 for each letter of s, subtracts 1 for each letter of t, and sums the magnitudes of the negative entries (the letters t has too many of).

Edge cases: t already an anagram of s, either identical or reordered, gives 0; disjoint letter sets give n; length-1 inputs give 0 or 1. Counting mismatched positions, counting distinct letters instead of multiplicities, or summing absolute differences over both sides (which double counts every step) are all wrong.

• Time complexity: O(n)
• Space complexity: O(1)