Katkat
Back

Minimum Character Replacements to Make One String an Anagram of Another

BloombergSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Given two strings of equal length made of lowercase letters, find the fewest single-character replacements in the second string that turn it into an anagram of the first. This phone-screen coding problem tests character frequency counting and precise reasoning about which letters must change.

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.