Lexicographically Smallest String After Reverse II - Solution & Explanation

Problem Overview: You are given a string and can reverse exactly one substring. The goal is to produce the lexicographically smallest possible string after the operation. The challenge is efficiently comparing many candidate strings without rebuilding and comparing full strings each time.

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

Try every possible substring [i, j], reverse it, and compare the resulting string with the current best. There are O(n^2) substrings and each comparison can take O(n). This leads to O(n^3) total time. The approach is straightforward and useful for reasoning about the problem, but it quickly becomes impractical for large inputs.

Approach 2: Rolling Hash + Binary Search Comparison (O(n log n) time, O(n) space)

The key observation is that most candidate strings share long prefixes. Instead of building full strings, compare them using prefix hashes. Precompute polynomial hashes for the original string and its reversed version using a hash function. When evaluating a candidate reversal, use binary search to find the longest common prefix between the current best string and the candidate. Rolling hash lets you compare substrings in O(1), so each comparison costs O(log n). Iterating over possible reversal boundaries while performing hashed comparisons reduces the total complexity dramatically.

Approach 3: Suffix Array Based Comparison (O(n log n) preprocessing, O(n log n) total)

Another method builds a suffix array and LCP structure for fast lexicographic comparisons. Each candidate produced by reversing a segment can be compared using suffix ranks and LCP queries rather than character-by-character checks. The preprocessing cost is higher, but once built, comparisons become efficient. This approach is more common in competitive programming environments where multiple string comparisons are required.

Recommended for interviews: The rolling hash + binary search approach usually strikes the best balance. Brute force demonstrates understanding of the transformation, but it fails for large constraints. Using hashed substring comparison shows you understand how to optimize lexicographic comparisons in String problems and handle many candidate transformations efficiently.