Skip to main content
Talentd

Lexicographically Smallest String After Reverse II - Solution & Explanation

HardPremiumFree on FleetCodeStringBinary SearchRolling HashSuffix Array3 min read
Practice this problem

Problem Statement

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:

  • reverse the first k characters of s, or
  • reverse the last k 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:

  • Choose k = 3, reverse the first 3 characters.
  • Reverse "dca" to "acd", resulting string s = "acdb", which is the lexicographically smallest string achievable.

Example 2:

Input: s = "abba"

Output: "aabb"

Explanation:

  • Choose k = 3, reverse the last 3 characters.
  • Reverse "bba" to "abb", so the resulting string is "aabb", which is the lexicographically smallest string achievable.

Example 3:

Input: s = "zxy"

Output: "xzy"

Explanation:

  • Choose k = 2, reverse the first 2 characters.
  • Reverse "zx" to "xz", so the resulting string is "xzy", which is the lexicographically smallest string achievable.

 

Constraints:

  • 1 <= n == s.length <= 105
  • s consists of lowercase English letters.

Approach Overview

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring ReversalO(n^3)O(n)Small inputs or verifying correctness during prototyping
Rolling Hash + Binary Search ComparisonO(n log n)O(n)General case with large strings and many candidate comparisons
Suffix Array + LCP QueriesO(n log n)O(n)When suffix array infrastructure already exists or multiple lexicographic comparisons are needed

Frequently Asked Questions

Is Lexicographically Smallest String After Reverse II easy or hard?
The problem is considered Hard because it combines string transformations with efficient lexicographic comparison. A naive solution is simple to write but too slow, while the optimized solution requires knowledge of rolling hash, binary search, or suffix array techniques.
Lexicographically Smallest String After Reverse II Python/Java solution
Most implementations follow the same structure across languages: compute prefix hashes, iterate over candidate reversal ranges, and compare results using binary search and substring hash checks. Python, Java, and C++ versions differ mainly in hash handling and modular arithmetic.
How to solve Lexicographically Smallest String After Reverse II in O(n log n)?
Precompute polynomial rolling hashes for the string and its reversed version. For each possible substring reversal, simulate the candidate string logically instead of building it. Use binary search to find the longest common prefix between two candidates and compare the next character using hash queries. This keeps each comparison to O(log n).
What is the best approach for Lexicographically Smallest String After Reverse II?
The most practical approach uses rolling hash with binary search to compare candidate strings. Precompute prefix hashes so substring comparisons take O(1). For each possible reversal, use binary search to find the first differing position between candidates. This reduces overall complexity to about O(n log n).
Is Lexicographically Smallest String After Reverse II asked at Google/Amazon/Meta?
String optimization problems involving lexicographic order, substring reversal, and hashing are common in interviews at companies like Google, Amazon, and Meta. Variants often test rolling hash, suffix arrays, or efficient substring comparison techniques.
What data structure is used in Lexicographically Smallest String After Reverse II?
Typical solutions rely on rolling hash arrays for fast substring hashing, along with binary search for prefix comparison. Some advanced implementations also use suffix arrays and LCP structures to perform lexicographic comparisons efficiently.
What is the time complexity of Lexicographically Smallest String After Reverse II?
The optimized solution using rolling hash and binary search runs in O(n log n) time with O(n) space. Brute force solutions that rebuild and compare strings require O(n^3) time because there are O(n^2) reversals and each comparison may scan the entire string.

Ready to solve this problem?

Practice Lexicographically Smallest String After Reverse II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring