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 lettersTo solve #2734 Lexicographically Smallest String After Substring Operation, the key idea is to minimize the string in lexicographical order by applying a single substring operation. Since decreasing characters earlier in the string has a larger impact on lexicographic order, a greedy strategy works well.
Traverse the string from left to right and locate the first character that is not 'a'. Once found, start a substring operation and reduce each character by one (for example, 'b' → 'a', 'c' → 'b') until you encounter an 'a' again or reach the end of the string. This ensures the earliest possible reduction in the string's order.
If the string consists entirely of 'a' characters, the optimal move is to modify the last character to 'z', which results in the smallest possible lexicographic change under the operation rules.
This greedy traversal ensures an efficient solution with O(n) time complexity and constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy traversal with substring character reduction | O(n) | O(1) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
When a character is replaced by the one that comes before it on the alphabet, it makes the string lexicographically smaller, except for ‘a'.
Find the leftmost substring that doesn’t contain the character 'a' and change all characters in it.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Lexicographic order is most affected by earlier characters in the string. By modifying the first possible non-'a' segment, the algorithm minimizes the string as early as possible, which guarantees the smallest possible result.
Problems involving greedy strategies and string manipulation are common in technical interviews at companies like FAANG. This question is a good practice example for understanding greedy decision making on strings.
No special data structure is required. The problem can be solved using simple string traversal and character manipulation, making it efficient with constant extra space.
The optimal approach uses a greedy strategy. Traverse the string to find the first character that is not 'a', then decrease consecutive characters by one until another 'a' appears or the string ends. This ensures the earliest lexicographic reduction.