Watch 4 video solutions for Lexicographically Smallest String After Reverse, a medium level problem involving Two Pointers, Binary Search, Enumeration. This walkthrough by R Sai Siddhu has 218 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s of length n consisting of lowercase English letters.
You must perform exactly one operation by choosing any integer k such that 1 <= k <= n and either:
k characters of s, ork characters of s.Return the lexicographically smallest string that can be obtained after exactly one such operation.
Example 1:
Input: s = "dcab"
Output: "acdb"
Explanation:
k = 3, reverse the first 3 characters."dca" to "acd", resulting string s = "acdb", which is the lexicographically smallest string achievable.Example 2:
Input: s = "abba"
Output: "aabb"
Explanation:
k = 3, reverse the last 3 characters."bba" to "abb", so the resulting string is "aabb", which is the lexicographically smallest string achievable.Example 3:
Input: s = "zxy"
Output: "xzy"
Explanation:
k = 2, reverse the first 2 characters."zx" to "xz", so the resulting string is "xzy", which is the lexicographically smallest string achievable.
Constraints:
1 <= n == s.length <= 1000s consists of lowercase English letters.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(n) | Good for understanding the problem or very small strings |
| Optimized Enumeration with Lazy Comparison | O(n^2) | O(n) | Preferred solution in interviews and competitive programming |