3675. Minimum Operations to Transform String

MediumGreedyString

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a string s that contains only lowercase English letters.

You can perform the following operation as many times as you want (including zero times):

Pick any character c that appears in the string, and replace every occurrence of c with the next letter in the alphabet.

For example, if you pick 'b', then all 'b' characters in the string become 'c' at the same time. This counts as one operation, no matter how many occurrences of 'b' there are.

Your goal is to find the minimum number of operations needed to turn the entire string into one made up of only 'a' characters.

Important detail: The alphabet is circular, meaning the letter after 'z' is 'a'.

Example

Suppose s = "yz":

The character 'y' needs to go 'y' → 'z' → 'a', which takes 2 steps.
The character 'z' needs to go 'z' → 'a', which takes 1 step.

Notice that when we advance 'y' to 'z', it merges with the existing 'z' characters, and from that point on they move together. So the total number of operations is determined by the character farthest from 'a' — in this case 'y', requiring 2 operations.

Key Observation

Since every occurrence of a character changes at once, and characters merge as they advance toward 'a', the answer is simply the largest distance from any character in the string to 'a', moving forward through the circular alphabet:

For a character c (where c != 'a'), its distance to 'a' is 26 - (ord(c) - ord('a')).
If the string already consists only of 'a' characters, the answer is 0.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Each character must reach 'a' along a circular one-way path, and characters merge as they advance; the farthest character absorbs every other one for free, so the answer is simply the maximum forward distance.

Open in Flowchart

Intuition

The first thing to notice is what an operation actually does: it shifts all occurrences of a chosen character forward by one letter, and it costs exactly one operation regardless of how many copies of that character exist in the string.

Now think about what happens as characters move toward 'a'. Every character must travel along the same one-way path: ... → 'x' → 'y' → 'z' → 'a'. There are no shortcuts and no alternative routes — the alphabet is circular, so the only direction is forward.

This leads to a crucial observation: characters merge along the way. Suppose the string contains both 'y' and 'z'. After one operation on 'y', those characters become 'z' and join the existing 'z' group. From that moment, they are indistinguishable and advance together for free — one operation moves all of them at once.

So the smartest strategy is to always push the character that is farthest from 'a' first. As it advances, it absorbs every other character it catches up to, and those absorbed characters cost nothing extra. By the time the farthest character reaches 'a', every other character has already been swept along with it.

Therefore, the total number of operations is simply the maximum distance from any character to 'a':

For a character c that is not 'a', the distance is 26 - (ord(c) - ord('a')), because we must wrap around the circular alphabet to reach 'a'.
Characters that are already 'a' need 0 operations and can be ignored.
If the string is made entirely of 'a', the answer is 0.

In short, the problem reduces from "transform the whole string" to "find the single character with the longest journey to 'a'" — everything else rides along for free.

Pattern Learn more about Greedy patterns.

Solution Approach

Single Pass

Based on the intuition, the answer is determined entirely by the character farthest from 'a'. This means we don't need any complex data structures or simulation — a single scan over the string is enough.

Steps:

Iterate through every character c in the string s.
Skip characters that are already 'a' — they require no operations.
Compute the distance to 'a' for each remaining character. Since the alphabet is circular, a character c must move forward 26 - (ord(c) - 97) steps to wrap around and land on 'a'. Here 97 is ord('a'), so:
- 'b' → 26 - 1 = 25 steps
- 'z' → 26 - 25 = 1 step
Take the maximum of all these distances. The farthest character absorbs every other character on its way to 'a', so its distance alone equals the total operation count.
Handle the edge case where the string contains only 'a' characters — the answer should be 0.

Implementation

class Solution:
    def minOperations(self, s: str) -> int:
        return max((26 - (ord(c) - 97) for c in s if c != "a"), default=0)

How the code maps to the steps:

The generator expression (26 - (ord(c) - 97) for c in s if c != "a") performs the single pass, filtering out 'a' characters and computing each distance on the fly without building an intermediate list.
max(..., default=0) selects the largest distance. The default=0 argument elegantly covers the edge case: if every character is 'a', the generator is empty and max returns 0 instead of raising an error.

Complexity Analysis

Time complexity: O(n), where n is the length of the string s. Each character is examined exactly once.
Space complexity: O(1). The generator evaluates lazily, so no extra storage proportional to the input size is needed.

Example Walkthrough

Let's trace through the solution with s = "axz".

Step 1: Scan each character and compute its distance to 'a'.

Character	Already `'a'`?	Distance Formula	Distance
`'a'`	Yes — skip	—	0
`'x'`	No	`26 - (ord('x') - 97) = 26 - 23`	3
`'z'`	No	`26 - (ord('z') - 97) = 26 - 25`	1

Step 2: Take the maximum distance.

The largest distance is 3, coming from 'x'. So the answer is 3.

Step 3: Verify by simulating the operations.

The farthest character 'x' sweeps up everything on its way to 'a':

Operation 1 — pick 'x': every 'x' becomes 'y'. String: "axz" → "ayz"
Operation 2 — pick 'y': every 'y' becomes 'z'. Now it merges with the existing 'z'. String: "ayz" → "azz"
Operation 3 — pick 'z': every 'z' becomes 'a' (wrapping around the circular alphabet). Both 'z' characters move together in a single operation. String: "azz" → "aaa" ✅

The simulation confirms it: even though 'z' needed 1 step on its own, it got absorbed into 'x''s journey for free. The total cost equals the longest individual journey — 3 operations.

Edge case check: if s = "aaa", the generator filters out every character, leaving it empty, and max(..., default=0) returns 0 — no operations needed.

Solution Implementation

1class Solution:
2    def minOperations(self, s: str) -> int:
3        # For each character that is not 'a', compute how many increment
4        # operations are needed to wrap it around back to 'a':
5        #   - ord(char) - ord('a') gives the character's offset from 'a'
6        #   - 26 - offset is the number of steps to cycle forward to 'a'
7        #
8        # The answer is the maximum number of steps among all such characters,
9        # because applying that many operations covers every other character
10        # along the way.
11        #
12        # If the string consists only of 'a' (the generator is empty),
13        # no operation is needed, so we fall back to the default value 0.
14        return max(
15            (26 - (ord(char) - ord("a")) for char in s if char != "a"),
16            default=0,
17        )
18

1class Solution {
2    /**
3     * Calculates the minimum number of operations required to convert
4     * every character in the string to 'a'.
5     *
6     * Each operation cyclically increments ALL characters of the string by one
7     * ('a' -> 'b', ..., 'z' -> 'a'). Therefore, a character c needs exactly
8     * (26 - (c - 'a')) increments to wrap around back to 'a', and the answer
9     * is determined by the character that needs the most increments.
10     *
11     * @param s the input string consisting of lowercase English letters
12     * @return the minimum number of operations needed
13     */
14    public int minOperations(String s) {
15        // Tracks the maximum number of increments needed among all characters
16        int maxIncrements = 0;
17
18        // Examine each character in the string
19        for (char currentChar : s.toCharArray()) {
20            // Characters that are already 'a' require no operations
21            if (currentChar != 'a') {
22                // Number of cyclic increments needed for this character to become 'a'
23                int incrementsNeeded = 26 - (currentChar - 'a');
24
25                // Keep the largest requirement, since all characters shift together
26                maxIncrements = Math.max(maxIncrements, incrementsNeeded);
27            }
28        }
29
30        return maxIncrements;
31    }
32}
33

1class Solution {
2public:
3    int minOperations(string s) {
4        // Tracks the minimum number of operations required.
5        int answer = 0;
6
7        // Iterate over each character in the string.
8        for (char ch : s) {
9            // Character 'a' needs no operation since it is already the target.
10            if (ch != 'a') {
11                // To turn 'ch' into 'a', we need (26 - (ch - 'a')) increments
12                // because the alphabet wraps around after 'z'.
13                // Each operation can be applied to a prefix/range, so the
14                // total operations needed is the maximum over all characters.
15                answer = max(answer, 26 - (ch - 'a'));
16            }
17        }
18
19        return answer;
20    }
21};
22

1/**
2 * Calculates the minimum number of operations needed,
3 * where each operation cyclically shifts characters forward,
4 * and every non-'a' character must eventually become 'a'.
5 *
6 * For a character c, it takes (26 - (c - 'a')) shifts to wrap around to 'a'.
7 * The answer is determined by the character requiring the most shifts.
8 *
9 * @param s - The input string consisting of lowercase English letters
10 * @returns The minimum number of operations required
11 */
12function minOperations(s: string): number {
13    // Tracks the maximum number of shifts needed among all characters
14    let maxShifts = 0;
15
16    // Iterate over each character in the string
17    for (const ch of s) {
18        // Characters that are already 'a' require no shifts
19        if (ch !== 'a') {
20            // Compute the shifts needed for this character to wrap to 'a'
21            const shiftsNeeded = 26 - (ch.charCodeAt(0) - 'a'.charCodeAt(0));
22
23            // Keep the largest shift count seen so far
24            maxShifts = Math.max(maxShifts, shiftsNeeded);
25        }
26    }
27
28    return maxShifts;
29}
30

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s. The code uses a generator expression to iterate through each character c in s exactly once. For each character, it performs constant-time operations: comparing c != "a", computing ord(c) - 97, and the subtraction 26 - (ord(c) - 97). The max function consumes this generator in a single pass, so the total work is proportional to the length of s.
Space Complexity: O(1). Since a generator expression is used instead of a list comprehension, the values are produced lazily one at a time and never materialized into a collection. Only a constant amount of extra space is needed to track the current maximum and the generator's state, regardless of the input size.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to handle the all-`'a'` string (empty generator crash)

A frequent mistake is writing the one-liner without the default argument:

# ❌ Buggy: raises ValueError when s = "aaa"
return max(26 - (ord(c) - 97) for c in s if c != "a")

When every character in s is 'a', the generator produces no values, and calling max() on an empty sequence raises:

ValueError: max() arg is an empty sequence

Solution: Always supply default=0 so the empty case gracefully returns 0:

# ✅ Correct
return max((26 - (ord(c) - 97) for c in s if c != "a"), default=0)

An equivalent fix is an explicit guard, which some find more readable:

if all(c == "a" for c in s):
    return 0
return max(26 - (ord(c) - 97) for c in s)

2. Computing the distance in the wrong direction

Another subtle bug is using the character's offset from 'a' rather than its circular distance to 'a':

# ❌ Buggy: measures distance backward, not forward through the cycle
return max((ord(c) - 97 for c in s), default=0)

This treats 'b' as 1 step away and 'z' as 25 steps away — exactly backwards. Operations only move characters forward ('b' → 'c' → ... → 'z' → 'a'), so 'z' is the closest non-'a' character (1 step) and 'b' is the farthest (25 steps).

Solution: Subtract the offset from 26 to measure the forward wrap-around distance: 26 - (ord(c) - 97).

3. Including `'a'` in the distance formula

If the filter if c != "a" is dropped, the formula assigns 'a' a distance of 26 - 0 = 26, since the math doesn't naturally yield 0 for 'a':

# ❌ Buggy: "aa" would return 26 instead of 0
return max((26 - (ord(c) - 97) for c in s), default=0)

This silently inflates the answer for any string containing 'a', and it's easy to miss because the code still runs without errors.

Solution: Either keep the explicit filter if c != "a", or use a modulo that maps 'a' to 0:

return max(((26 - (ord(c) - 97)) % 26 for c in s), default=0)

4. Summing distances instead of taking the maximum

A conceptual misunderstanding is to count operations per distinct character and add them up:

# ❌ Buggy: overcounts because merged characters share operations
return sum(26 - (ord(c) - 97) for c in set(s) if c != "a")

For s = "yz", this returns 2 + 1 = 3 instead of 2. The key insight is that as a character advances, it merges with characters ahead of it and they move together from then on. The farthest character's journey to 'a' necessarily passes through (and absorbs) every other character, so the maximum distance alone is the answer — not the sum.

Solution: Use max, trusting that the merging behavior makes all shorter journeys "free" once the longest journey is paid for.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don't know