Given a string s consisting of lowercase English letters. Perform the following operation:
Return the lexicographically smallest string after performing the operation.
Example 1:
Input: s = "cbabc"
Output: "baabc"
Explanation:
Perform the operation on the substring starting at index 0, and ending at index 1 inclusive.
Example 2:
Input: s = "aa"
Output: "az"
Explanation:
Perform the operation on the last letter.
Example 3:
Input: s = "acbbc"
Output: "abaab"
Explanation:
Perform the operation on the substring starting at index 1, and ending at index 4 inclusive.
Example 4:
Input: s = "leetcode"
Output: "kddsbncd"
Explanation:
Perform the operation on the entire string.
Constraints:
1 <= s.length <= 3 * 105s consists of lowercase English lettersProblem Overview: You are given a lowercase string and can choose exactly one non-empty substring. For every character in that substring, decrease it by one in the alphabet ('b' → 'a', 'a' → 'z'). The goal is to produce the lexicographically smallest possible string after the operation.
Approach 1: Single Scan with Immediate Replacement (O(n) time, O(1) space)
This greedy strategy scans the string from left to right and looks for the first character that is not 'a'. Once found, you start a substring and keep decrementing characters until you hit another 'a'. Decreasing earlier characters has the strongest effect on lexicographic order, so starting at the first non-'a' position guarantees the smallest possible prefix. Each character in the selected segment is reduced by one using a simple character shift. If the string consists entirely of 'a', the optimal move is to change the last character to 'z'. This approach performs a single pass and uses constant extra memory.
This technique relies on a greedy observation: modifying the earliest possible position produces the biggest lexicographic improvement. The logic mainly involves iterating over characters and performing in-place updates, making it a clean example of greedy reasoning applied to a string manipulation problem.
Approach 2: Reverse String and Apply (O(n) time, O(n) space)
Another way to reason about the operation is by reversing the string and processing the transformation from the end. After reversing, you locate the first character that can be decremented without breaking the greedy condition and apply the same decrement logic over the contiguous segment. Once the transformation is complete, reverse the string again to restore the original order. This approach simplifies certain implementations where processing from the tail is more intuitive.
Although it introduces an extra reverse step and temporary storage, the overall time complexity remains linear. The algorithm still performs constant work per character and maintains predictable behavior for edge cases such as strings composed entirely of 'a'.
Recommended for interviews: The single-scan greedy solution is what most interviewers expect. It demonstrates that you understand how lexicographic order works and why modifying the earliest non-'a' character minimizes the result. Mentioning the reverse-processing idea can show deeper reasoning, but implementing the linear greedy scan clearly signals strong problem-solving skills.
This approach involves scanning through the string once and beginning the replacement operation the moment we encounter the first character that is greater than 'a'. We continue replacing characters until either a 'a' is encountered again or we reach the end of the string. This single-pass approach ensures the transformation is performed instantaneously when the optimal condition is detected.
The solution uses a for loop to traverse the string character by character. When it encounters a character greater than 'a', it decrements the character by one, indicating it's replaced by its preceding alphabet, and sets a change flag. If it encounters a 'a' while the change flag is set, it breaks the loop, completing the operation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string, as each character is processed only once.
Space Complexity: O(1), as the transformation is performed in place.
This method involves reversing the string and applying the replacement operation in reverse order. It ensures that any leading 'a' characters in the reversed string don't interfere with the operation, potentially providing an alternative path to reach the solution efficiently.
This solution reverses the string first to evaluate operations from a different start perspective. After abbreviating eligible characters and the operation halts with encountering an 'a', it restores the string back for the final output.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), due to reverse operations and the traversal.
Space Complexity: O(1), as operations are in place.
| Approach | Complexity |
|---|---|
| Single Scan with Immediate Replacement | Time Complexity: O(n), where n is the length of the string, as each character is processed only once. |
| Reverse String and Apply | Time Complexity: O(n), due to reverse operations and the traversal. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Scan with Immediate Replacement | O(n) | O(1) | Best general solution. Minimal memory and optimal greedy logic. |
| Reverse String and Apply | O(n) | O(n) | Useful when implementing transformations from the end or when reverse traversal simplifies reasoning. |
Sliding Window Algorithm Explained Clearly | Longest Substring Without Repeating Characters Leetcode • Greg Hogg • 84,044 views views
Watch 9 more video solutions →Practice Lexicographically Smallest String After Substring Operation with our built-in code editor and test cases.
Practice on FleetCode