Minimum Character Replacements to Make One String an Anagram of Another
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
Input: s = "night", t = "thing"
Output: 0
```
`t` already contains the same letters as `s`, each the same number of times.
**Example 3**
```text
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.
Overview: 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.
**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`.
Return the answer as a single integer.
**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 never exceeds 2^31 - 1 and fits in a 32-bit signed integer (`int` in Java and C++).
**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 = "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.
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 never exceeds 2^31 - 1 and fits in a 32-bit signed integer.
Examples
Input: ('a', 'a')
Expected Output: 0
Explanation: Minimum length with the same letter: already an anagram.
Input: ('a', 'b')
Expected Output: 1
Explanation: Minimum length with different letters: one replacement.
Hints
- Anagrams ignore order, so think about what information about each string actually decides whether two strings are anagrams.
- Each step changes one character of t into another letter. Ask which characters of t could be left untouched.
- The two strings have the same length, so whatever t has too much of is balanced by what it lacks.