Lexicographically Smallest String After Substring Operation

Lexicographically Smallest String After Substring Operation

What is this problem about?

The "Lexicographically Smallest String After Substring Operation interview question" involves selecting exactly one non-empty substring and replacing each character in it with its preceding character in the alphabet (e.g., 'b' becomes 'a', 'c' becomes 'b'). If the character is 'a', it wraps around to 'z'. Your goal is to find the lexicographically smallest string possible after this single operation. This "Lexicographically Smallest String After Substring Operation coding problem" is a classic test of greedy optimization under a single-transformation constraint.

Why is this asked in interviews?

This problem is popular at companies like Goldman Sachs and Amazon because it tests a candidate's understanding of the "Greedy interview pattern". It evaluates whether you can identify the optimal place to start and stop the transformation. Since a string's lexicographical value is dominated by its leftmost characters, the problem checks if you can find the first character that can be "improved" (made smaller) and how far that improvement can be extended.

Algorithmic pattern used

The Greedy approach is the standard solution. You should find the first character in the string that is NOT 'a'. Starting from that character, decrement every subsequent character until you either reach an 'a' or hit the end of the string. Why stop at 'a'? Because 'a' would turn into 'z', making the string lexicographically larger. If the entire string consists of 'a's, you must change the very last 'a' to 'z' because the problem requires a non-empty substring.

Example explanation

String: "aaabcc"

1. Skip 'a's: The first three characters are 'a'. We leave them alone.
2. First non-'a': We find 'b' at index 3.
3. Start operation: Change 'b' to 'a'. String: "aaaacc"
4. Continue: Change 'c' to 'b'. String: "aaaabcc" -> "aaaab b"
5. Stop: The next char is 'c', change to 'b'. "aaaab b" Result: "aaaabbb" (if the operation continued) or "aaaabbc" (if it stopped before the last c).

Common mistakes candidates make

• Changing 'a' to 'z': Forgetting that 'z' is lexicographically larger than 'a', so you should avoid transforming 'a' whenever possible.
• Not handling all 'a's: Failing the case where the string is "aaaa", where you must change at least one character.
• Multiple substrings: Applying the operation to more than one disconnected substring.

Interview preparation tip

In lexicographical problems, always focus on the first character you can change. If you can make a character smaller without making any preceding character larger, you've improved the string.