Lexicographically Smallest String After Substring Operation - Solution & Explanation

Problem 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.