Problem Breakdown
We are given two strings s and t, guaranteed to be of equal length containing only lowercase English letters. The goal is to transform string t into an anagram of string s. An operation consists of picking one character in t and replacing it with another. We need the minimum number of such operations.
Key Constraints & Inputs:
- Inputs: Two strings,
sandt, wherelen(s) == len(t)and length is between 1 and 50,000. - Output: An integer representing the count of replacements needed.
- Implicit Constraint: Since order doesn’t matter for anagrams (only character counts), we can ignore string positions entirely. We are essentially comparing histograms.
Intuition
A brute-force approach would involve trying to replace characters at every position of t with every possible lowercase letter and checking validity, which leads to exponential or high polynomial complexity ( per step). This is inefficient for .
Key Insight:
Anagrams are defined solely by character frequency counts. If string s requires three ‘a’s but string t currently has only one ‘a’, we must perform exactly two replacements to create the missing ‘a’s in t. The characters being replaced don’t need specific tracking; they just fill whatever deficit exists elsewhere.
Therefore, for every character type (e.g., ‘a’ through ‘z’), if s contains more instances than t, that difference represents a “deficit” we must fix via replacement steps. If t has more of a certain character than s, those excess characters in t are simply the ones being replaced to satisfy other deficits, so they don’t contribute positively to our step count directly (we only care about what is missing).
Approach
- Frequency Counting: Initialize an array or hash map to track counts of each character ‘a’-‘z’.
- Populate
s: Iterate through stringsand increment the frequency for each encountered character. This represents our target distribution. - Adjust with
t: Iterate through stringt. For every character found, decrement its count in our map (representing a match). If we encounter a character that isn’t needed or has already been matched againsts, it effectively counts as an excess to be replaced later. - Calculate Deficit: After processing both strings, the frequency array will contain positive values for characters where
tis short compared tos. Negative values represent characters intthat are surplus (which we don’t need to count towards steps). The sum of all remaining positive frequencies gives us exactly how many replacements are needed.
Complexity Analysis
- Time Complexity: , where is the length of string
s. We iterate through both strings once ( operations) and perform constant-time updates to a fixed-size array (size 26). - Space Complexity: relative to input size. While we allocate an array, its size depends on the alphabet size (fixed at 26 for lowercase English), not the length of
s. Thus, it is effectively constant space.
Solution
class Solution:
def minSteps(self, s: str, t: str) -> int:
# Frequency array to store counts of characters 'a' through 'z'.
# Index 0 represents 'a', index 25 represents 'z'.
freq = [0] * 26
base_ord = ord('a')
# Increment count for every character in s (target requirements)
for char in s:
freq[ord(char) - base_ord] += 1
# Decrement count for every character in t (what we currently have)
# If a value drops below zero, it means t has more of this char than needed.
# We only care about positive remainders at the end.
for char in t:
freq[ord(char) - base_ord] -= 1
# Sum all positive values remaining in frequency array.
# These represent characters missing from t that must be created via replacement.
return sum(count for count in freq if count > 0)
Edge Cases Handled
- Identical Strings: The loop over
twill perfectly decrement the counts set bys, resulting in all zeros, and returning a step count of 0. - No Overlap (e.g., s=“abc”, t=“def”): All characters from
sremain positive after processingt. Sum returns (length), which is correct as every character must be replaced. - Surplus Characters in
t: Ifthas more of a specific letter thans, the frequency count for that letter becomes negative or zero, and these are excluded from the final sum via the positive check (if count > 0).