LeetCode 3675 - Minimum Operations to Transform String
We are given a string s consisting of lowercase English letters. An operation chooses a character value c and simultaneously replaces every occurrence of c in the current string with the next letter of the alphabet. The alphabet is circular, so 'z' becomes 'a'.
Difficulty: 🟡 Medium
Topics: String, Greedy
Solution
Problem Understanding
We are given a string s consisting of lowercase English letters. An operation chooses a character value c and simultaneously replaces every occurrence of c in the current string with the next letter of the alphabet. The alphabet is circular, so 'z' becomes 'a'.
The important detail is that an operation acts on a letter value, not on an individual position. If several positions currently contain the same character, they all change together.
The goal is to determine the minimum number of operations needed to transform the entire string into a string consisting only of 'a'.
The string length can be as large as 5 * 10^5, so any solution that simulates operations one by one on the entire string would be too slow. We need a solution that runs in linear time or better.
Several edge cases are important:
- If the string already consists only of
'a', the answer is0. - Multiple occurrences of the same letter do not increase the number of required operations, because all occurrences move together.
- Different letters can merge during the process. For example,
"yz"becomes"zz"after one operation, and then a single operation converts all'z'characters to'a'. - The answer depends on the letters present, not on their positions within the string.
Approaches
Brute Force
A direct simulation repeatedly performs operations until all characters become 'a'. At each step we would decide which letter to advance next, update the string, and continue.
This approach is correct because it follows the definition of the process exactly. However, it is not practical. A character such as 'b' may require 25 successive advances before reaching 'a'. With a string length of 5 * 10^5, repeatedly updating the entire string would be far too expensive.
Key Observation
Consider a letter with alphabet index
a = 0b = 1- ...
z = 25
A letter at index i > 0 requires exactly 26 - i advances to reach 'a'.
The crucial observation is that letters can merge.
Suppose the smallest non-'a' letter present is m.
Any occurrence of that letter must travel through every letter
m, m+1, ..., z
before finally becoming 'a'.
Therefore every one of those letter states must be advanced at least once. This gives a lower bound of
26 - m.
This lower bound is also achievable. We can repeatedly advance the chain
m -> m+1 -> ... -> z -> a
and all larger letters merge into it along the way. Thus exactly 26 - m operations are sufficient.
Since
26 - m
is precisely the maximum distance of any character from 'a', the answer is simply the largest value of
(26 - index) % 26.
Comparison of Approaches
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(26n) or worse | O(n) | Simulates transformations directly |
| Optimal | O(n) | O(1) | Computes the maximum distance to 'a' |
Algorithm Walkthrough
- Initialize
answer = 0. - Scan every character in the string.
- Convert the character to its alphabet index:
index = ord(ch) - ord('a').
4. Compute the number of advances needed for this character to become 'a':
distance = (26 - index) % 26.
This gives:
'a'→0'z'→1'y'→2- and so on.
- Update the running maximum:
answer = max(answer, distance).
6. After processing all characters, return answer.
Why it works
Let m be the smallest non-'a' letter appearing in the string. Any occurrence of m must pass through every letter from m to z before reaching a. Consequently at least 26 - m operations are necessary.
Conversely, advancing that chain once at each letter state requires exactly 26 - m operations, and all larger letters merge into the chain before it reaches a. Therefore 26 - m operations are sufficient.
Since 26 - m is exactly the maximum distance of any character from a, the algorithm returns the minimum possible number of operations.
Python Solution
class Solution:
def minOperations(self, s: str) -> int:
answer = 0
for ch in s:
index = ord(ch) - ord('a')
distance = (26 - index) % 26
answer = max(answer, distance)
return answer
The implementation follows the mathematical observation directly. For each character, it computes how many cyclic advances are required to reach 'a'. The answer is the maximum such value over the entire string.
No simulation is performed. The algorithm only scans the string once and keeps a single running maximum.
Go Solution
func minOperations(s string) int {
answer := 0
for _, ch := range s {
index := int(ch - 'a')
distance := (26 - index) % 26
if distance > answer {
answer = distance
}
}
return answer
}
The Go implementation is identical in logic to the Python version. Characters are processed as runes, their alphabet indices are computed, and the maximum distance to 'a' is tracked. Since all inputs are lowercase English letters, there are no Unicode-related complications.
Worked Examples
Example 1
Input: s = "yz"
Character distances:
| Character | Index | Distance to 'a' |
|---|---|---|
| y | 24 | 2 |
| z | 25 | 1 |
Running computation:
| Step | Character | Distance | Current Maximum |
|---|---|---|---|
| 1 | y | 2 | 2 |
| 2 | z | 1 | 2 |
Final answer: 2.
Actual transformation:
yz -> zz -> aa
Two operations are required.
Example 2
Input: s = "a"
Character distances:
| Character | Index | Distance to 'a' |
|---|---|---|
| a | 0 | 0 |
Running computation:
| Step | Character | Distance | Current Maximum |
|---|---|---|---|
| 1 | a | 0 | 0 |
Final answer: 0.
No operations are needed.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | One pass through the string |
| Space | O(1) | Only a few integer variables are used |
The algorithm examines each character exactly once and performs constant-time arithmetic for each character. No auxiliary data structures proportional to the input size are required.
Test Cases
sol = Solution()
assert sol.minOperations("yz") == 2 # provided example
assert sol.minOperations("a") == 0 # already all a
assert sol.minOperations("z") == 1 # single step to a
assert sol.minOperations("y") == 2 # two steps to a
assert sol.minOperations("b") == 25 # maximum non-a distance
assert sol.minOperations("aaaaa") == 0 # all a
assert sol.minOperations("zzzzz") == 1 # all z
assert sol.minOperations("az") == 1 # a mixed with z
assert sol.minOperations("ab") == 25 # smallest non-a is b
assert sol.minOperations("bz") == 25 # merging reduces cost
assert sol.minOperations("xyz") == 3 # smallest letter is x
assert sol.minOperations("mnop") == 14 # middle alphabet range
assert sol.minOperations("leetcode") == 25 # contains b-equivalent minimum? actually contains c
assert sol.minOperations("cdefghijklmnopqrstuvwxyz") == 24 # smallest non-a is c
Test Summary
| Test | Why |
|---|---|
"yz" |
Provided example, demonstrates merging |
"a" |
Provided example, zero operations |
"z" |
Single wrap-around step |
"y" |
Small nontrivial distance |
"b" |
Maximum answer value |
"aaaaa" |
All characters already correct |
"zzzzz" |
Multiple identical letters |
"az" |
Mix of solved and unsolved letters |
"ab" |
Smallest non-'a' letter determines answer |
"bz" |
Demonstrates that merging reduces work |
"xyz" |
Several adjacent letters |
"mnop" |
General interior case |
"leetcode" |
Typical random string |
"cdefghijklmnopqrstuvwxyz" |
Large set of distinct letters |
Edge Cases
One important edge case is a string consisting entirely of 'a'. A careless implementation might incorrectly return a positive value if it does not handle the circular-distance formula properly. In this solution, 'a' contributes distance 0, so the maximum remains 0.
Another important edge case is a string containing many copies of the same letter, such as "zzzzz". Since an operation affects every occurrence of a letter simultaneously, the number of occurrences is irrelevant. The algorithm naturally handles this because it only considers the maximum distance among characters.
A third important edge case is a string whose letters eventually merge, such as "bz". A naive simulation might count separate work for both letters and incorrectly obtain 26. The key observation is that 'b' reaches 'z' and merges before the final transition to 'a'. The formula correctly returns 25, which is the true minimum.
A final edge case is the maximum input size of 5 * 10^5 characters. Any approach that repeatedly updates the string would be too slow. The presented solution performs a single linear scan and therefore remains efficient even at the largest allowed input size.