#2734

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Lexicographically Smallest String After Substring Operation

Given a string, perform operations to make it lexicographically smaller using a greedy approach with substring modifications.

string greedy

Problem Statement

You are given a string s of lowercase English letters. You can perform the following operation: select a substring and replace each character with the character that precedes it in the alphabet, except for 'a' which remains unchanged. The goal is to perform the operation on the string such that the resulting string is the lexicographically smallest possible.

Return the lexicographically smallest string you can get after performing the operation on one or more substrings.

Examples

Example 1

Input: s = "cbabc"

Output: "baabc"

Perform the operation on the substring starting at index 0, and ending at index 1 inclusive.

Example 2

Input: s = "aa"

Output: "az"

Perform the operation on the last letter.

Example 3

Input: s = "acbbc"

Output: "abaab"

Perform the operation on the substring starting at index 1, and ending at index 4 inclusive.

Constraints

1 <= s.length <= 3 * 105
s consists of lowercase English letters

Solution Approach

Greedy Character Replacement

To minimize the string lexicographically, iterate through the string and for each character, check if replacing it with its preceding character ('a' excluded) results in a smaller string. This greedy approach ensures that the leftmost possible characters are changed first, leading to an overall smaller string.

Invariant Validation

The invariant is that any change to a character must still result in a valid string, and the transformation can only occur when the new character is lexicographically smaller than the current one. This validation ensures that we don't make an operation that reverses progress or increases the string value.

Efficient Traversal

Traverse the string from left to right and apply the operation to each character where beneficial. This approach ensures that every character is considered in its context, and the decision to apply the operation is made locally to achieve a globally smallest string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the traversal approach. If each character is processed once, the time complexity is O(n), where n is the length of the string. The space complexity is O(1) since only a few variables are used to track modifications during the traversal.

What Interviewers Usually Probe

Ensure the candidate uses a greedy approach to minimize the string.
Look for an understanding of when and why changes to characters are valid.
Evaluate if the candidate can efficiently handle the traversal of large strings.

Common Pitfalls or Variants

Common pitfalls

Failing to consider the lexicographical order properly by making unnecessary changes to characters that don't improve the result.
Not correctly handling the edge case where a character is 'a', which can't be reduced further.
Trying to modify characters in the wrong order, potentially missing the smallest lexicographical result.

Follow-up variants

Implementing this approach using different data structures, such as a stack or deque.
Optimizing for the case where the string is already lexicographically minimal.
Applying this greedy strategy to strings containing non-alphabetical characters or uppercase letters.

FAQ

What is the Lexicographically Smallest String After Substring Operation problem?

This problem asks you to transform a string into its lexicographically smallest form by performing an operation on substrings, where each character can be replaced with its preceding character in the alphabet, except 'a'.

How do I solve the Lexicographically Smallest String After Substring Operation problem?

Use a greedy approach by replacing each character with the previous one in the alphabet (except for 'a') to make the string lexicographically smaller, starting from the leftmost characters.

What is the time complexity of solving this problem?

The time complexity is O(n), where n is the length of the string, since each character is processed once during the traversal.

What is the key to solving this problem?

The key is recognizing when to apply the greedy replacement operation and ensuring that each operation results in a lexicographically smaller string.

What common mistakes should I avoid in the Lexicographically Smallest String After Substring Operation problem?

Avoid overcomplicating the solution by changing characters unnecessarily or ignoring the edge case of 'a' which can't be reduced further.

terminal

Solution

Solution 1: Greedy Algorithm

We can traverse the string $s$ from left to right, find the position $i$ of the first character that is not 'a', and then find the position $j$ of the first 'a' character starting from $i$. We decrement each character in $s[i:j]$, and finally return the processed string.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    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[:-1] + "z"
        j = i
        while j < n and s[j] != "a":
            j += 1
        return s[:i] + "".join(chr(ord(c) - 1) for c in s[i:j]) + s[j:]

Continue Practicing

#2712 minimum cost to make all characters equal #2697 lexicographically smallest palindrome #2800 shortest string that contains three strings