Lexicographically Smallest String After Reverse - Solution & Explanation

Problem Overview: You are given a string and can reverse exactly one substring. The goal is to choose the substring that produces the lexicographically smallest possible result. The challenge is deciding which segment [l, r] to reverse so the resulting string is minimal in dictionary order.

Approach 1: Brute Force Enumeration (O(n^3) time, O(n) space)

The most direct strategy is to try every possible substring reversal. For each pair of indices l and r, reverse the substring s[l:r] and construct the resulting string. Compare it with the current best answer and keep the lexicographically smallest one. This requires generating a new string for each candidate, which costs O(n), while the number of pairs is O(n^2). Total complexity becomes O(n^3) time with O(n) extra space for temporary strings. This brute force approach is useful for understanding the search space but becomes slow for larger inputs.

Approach 2: Optimized Enumeration (O(n^2) time, O(n) space)

You can avoid repeatedly rebuilding full strings by comparing candidates more carefully. Iterate over all starting positions l, and for each l try every possible end position r. Instead of constructing the full reversed string every time, simulate the comparison against the current best answer character by character. The prefix before l stays the same, while the reversed section is accessed using mirrored indices. This reduces the cost of each check and avoids unnecessary copying. The overall process still enumerates O(n^2) substrings, but each comparison exits early once a difference is found, making it practical in typical constraints.

This approach naturally relates to techniques from enumeration, where you systematically explore candidate ranges. During comparison, you effectively simulate reversed traversal similar to a two pointers pattern. Some optimized implementations also use ideas similar to binary search style comparisons when checking lexicographic differences quickly.

Recommended for interviews: Interviewers expect the optimized enumeration solution. Starting with brute force shows you understand the operation space (all [l, r] reversals). Then reduce redundant string construction and compare lazily to reach O(n^2) time. This demonstrates both correctness reasoning and practical optimization.