Problem Description

You are given a string s consisting of lowercase English letters. You need to perform exactly one operation on this string to make it lexicographically smallest.

The operation allows you to:

• Select any non-empty substring from s
• Replace every letter in that substring with the preceding letter in the English alphabet
  • For example: 'b' becomes 'a', 'c' becomes 'b', and so on
  • Special case: 'a' wraps around to become 'z'

Your goal is to return the lexicographically smallest string possible after performing this operation exactly once.

For example:

• If s = "cbabc", you could select the substring "cba" and transform it to "baz", resulting in "bazbc"
• If s = "acbbc", you could select the substring "cbbc" and transform it to "baab", resulting in "abaab"
• If s = "aaa", since all characters are already 'a', the best strategy is to change the last 'a' to 'z', resulting in "aaz"

The key insight is that to get the lexicographically smallest result, you want to:

1. Skip any leading 'a' characters (since changing 'a' to 'z' makes it larger)
2. Find the first non-'a' character and start the operation there
3. Continue the operation until you hit another 'a' or reach the end of the string
4. If the entire string is all 'a's, change only the last character to 'z'

Intuition

To make the string lexicographically smallest, we need to think about which substring to select and transform. Since we want the smallest possible result, we should focus on making the leftmost characters as small as possible.

Let's think about what happens when we apply the operation:

• Characters like 'b', 'c', 'd' become 'a', 'b', 'c' respectively - they get smaller
• The character 'a' becomes 'z' - it gets larger

This tells us that we should avoid transforming 'a' characters whenever possible, as turning 'a' into 'z' makes the string larger, not smaller.

The greedy strategy emerges from this observation:

1. We want to start our transformation as early as possible in the string to affect the most significant positions
2. But we should skip any leading 'a' characters since transforming them would make the string larger
3. Once we find the first non-'a' character, we should start our transformation there
4. We should continue the transformation as long as we encounter non-'a' characters, because each transformation makes those characters smaller
5. We should stop when we hit another 'a', because including it in our transformation would turn it into 'z', making the string larger

The special case is when the entire string consists only of 'a' characters. In this situation, we must perform the operation (as required by the problem), so the best we can do is transform just the last 'a' to 'z'. This minimizes the impact on the lexicographical order since the last position is the least significant.

For example, with s = "acbbc":

• Skip the leading 'a'
• Start transforming from 'c' at position 1
• Continue through all non-'a' characters: "cbbc" → "baab"
• Result: "abaab"

This greedy approach guarantees the lexicographically smallest result because we're making the earliest possible non-'a' characters smaller while avoiding making any 'a' characters larger (except when unavoidable).

Learn more about Greedy patterns.

Solution Approach

The implementation follows a greedy algorithm with two pointers to identify the optimal substring to transform:

Step 1: Find the starting position

i = 0
while i < n and s[i] == "a":
    i += 1

We traverse from the beginning of the string to find the first non-'a' character. This position i marks where our transformation should begin, as we want to skip all leading 'a' characters.

Step 2: Handle the special case

if i == n:
    return s[:-1] + "z"

If i reaches the end of the string (i == n), it means the entire string consists only of 'a' characters. In this case, we must still perform the operation, so we transform only the last character from 'a' to 'z' to minimize the lexicographical impact.

Step 3: Find the ending position

j = i
while j < n and s[j] != "a":
    j += 1

Starting from position i, we find the first 'a' character or reach the end of the string. This position j marks where our transformation should end, as we want to transform all consecutive non-'a' characters.

Step 4: Perform the transformation

return s[:i] + "".join(chr(ord(c) - 1) for c in s[i:j]) + s[j:]

We construct the result by:

• Keeping the prefix s[:i] unchanged (all the leading 'a' characters)
• Transforming the substring s[i:j] by decrementing each character using chr(ord(c) - 1)
• Keeping the suffix s[j:] unchanged (everything after our selected substring)

The transformation uses ASCII values: ord(c) gets the ASCII value of character c, we subtract 1 to get the previous letter, and chr() converts it back to a character.

Time Complexity: O(n) where n is the length of the string, as we traverse the string once and perform the transformation in linear time.

Space Complexity: O(n) for creating the result string.

Example Walkthrough

Let's walk through the solution with the example s = "acbbc":

Step 1: Find the starting position

• Start at index 0: s[0] = 'a'
• Since it's an 'a', increment i to 1
• Check s[1] = 'c' (not 'a'), so stop here
• Starting position i = 1

Step 2: Check for special case

• Since i = 1 (not equal to string length 5), this is not an all-'a' string
• Continue to step 3

Step 3: Find the ending position

• Start from j = i = 1
• s[1] = 'c' (not 'a'), increment j to 2
• s[2] = 'b' (not 'a'), increment j to 3
• s[3] = 'b' (not 'a'), increment j to 4
• s[4] = 'c' (not 'a'), increment j to 5
• Reached end of string, so j = 5

Step 4: Perform the transformation

• Prefix (unchanged): s[0:1] = "a"
• Substring to transform: s[1:5] = "cbbc"
  • 'c' → 'b' (ASCII 99 → 98)
  • 'b' → 'a' (ASCII 98 → 97)
  • 'b' → 'a' (ASCII 98 → 97)
  • 'c' → 'b' (ASCII 99 → 98)
  • Transformed substring: "baab"
• Suffix (unchanged): s[5:] = "" (empty)

Final result: "a" + "baab" + "" = "abaab"

This is lexicographically smaller than the original "acbbc" because we've made all the non-'a' characters smaller while avoiding turning any 'a' into 'z'.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

The algorithm performs the following operations:

• First while loop: iterates through the string to skip leading 'a' characters - O(n) in worst case
• Second while loop: iterates through the string to find the next 'a' character - O(n) in worst case
• String slicing operations s[:i], s[i:j], and s[j:] - each takes O(n) in worst case
• The join operation with list comprehension iterates through at most n characters - O(n)
• Character operations chr(ord(c) - 1) are O(1) for each character

Since all operations are sequential and each is at most O(n), the overall time complexity is O(n).

Space Complexity: O(n), where n is the length of the string s.

The space usage includes:

• The list comprehension [chr(ord(c) - 1) for c in s[i:j]] creates a new list that can contain up to n characters - O(n)
• String slicing creates new string objects for s[:i], s[i:j], and s[j:] - O(n) in total
• The final concatenated string result - O(n)
• Variables i, j, and n use constant space - O(1)

The dominant space usage comes from creating new strings and the intermediate list, resulting in O(n) space complexity.

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

Common Pitfalls

1. Forgetting the "Exactly Once" Requirement

Pitfall: A common mistake is focusing only on making the string lexicographically smallest without ensuring the operation is performed exactly once. This leads to incorrect handling of strings consisting entirely of 'a' characters.

Incorrect approach:

# Wrong: Returns the original string without performing any operation
def smallestString(self, s: str) -> str:
    n = len(s)
    i = 0
    while i < n and s[i] == 'a':
        i += 1
  
    if i == n:
        return s  # ERROR: No operation performed!
  
    # ... rest of the code

Why it's wrong: For input like s = "aaa", this would return "aaa" without performing any operation, violating the constraint that we must perform exactly one operation.

Correct solution: Always perform the operation, even if it makes the string lexicographically larger:

if i == n:
    return s[:-1] + 'z'  # Transform the last 'a' to 'z'

2. Incorrectly Handling Character Wrap-Around

Pitfall: Forgetting that 'a' should wrap around to 'z' when decreased, not become an invalid character.

Incorrect approach:

# Wrong: Blindly decrements all characters without handling 'a' specially
def smallestString(self, s: str) -> str:
    # Find any substring and decrease all characters
    result = ""
    for i in range(len(s)):
        result += chr(ord(s[i]) - 1)  # ERROR: 'a' becomes '`' (invalid)
    return result

Why it's wrong: The ASCII value of 'a' is 97, and subtracting 1 gives 96, which is the backtick character '`', not 'z'.

Correct solution: Handle the wrap-around case explicitly:

def decrease_char(c):
    if c == 'a':
        return 'z'
    else:
        return chr(ord(c) - 1)

However, the optimal algorithm avoids this issue by strategically selecting substrings that don't contain 'a' (except for the special all-'a' case).

3. Selecting the Wrong Substring

Pitfall: Choosing a substring that doesn't lead to the lexicographically smallest result, such as transforming characters that are already 'a' or stopping the transformation too early.

Incorrect approach:

# Wrong: Transforms only the first non-'a' character
def smallestString(self, s: str) -> str:
    for i in range(len(s)):
        if s[i] != 'a':
            return s[:i] + chr(ord(s[i]) - 1) + s[i+1:]
    return s[:-1] + 'z'

Why it's wrong: For input s = "bcb", this would transform only the first 'b' to get "acb", but the optimal solution is to transform "bcb" entirely to get "aba".

Correct solution: Transform all consecutive non-'a' characters starting from the first non-'a':

j = i
while j < n and s[j] != 'a':
    j += 1
# Transform the entire substring s[i:j]

4. Off-by-One Errors in Substring Selection

Pitfall: Incorrectly handling the indices when slicing the string, leading to missing characters or including wrong characters in the transformation.

Incorrect approach:

# Wrong: Incorrect slicing
result = s[:i-1] + modified + s[j+1:]  # ERROR: Wrong indices

Correct solution: Use proper Python slicing conventions:

result = s[:i] + modified_substring + s[j:]

Remember that s[:i] includes characters from index 0 to i-1, and s[j:] includes characters from index j to the end.