LeetCode 3735 - Lexicographically Smallest String After Reverse II
The problem is asking us to manipulate a string s of length n in order to produce the lexicographically smallest possible string after exactly one operation.
Difficulty: 🔴 Hard
Topics: String, Binary Search, Rolling Hash, Suffix Array, Hash Function
Solution
Problem Understanding
The problem is asking us to manipulate a string s of length n in order to produce the lexicographically smallest possible string after exactly one operation. The operation allows you to choose an integer k between 1 and n and either reverse the first k characters or reverse the last k characters.
The input string consists only of lowercase English letters, which allows us to compare characters using standard lexicographical ordering. The output is a single string that results from performing exactly one valid operation, and it must be the smallest string in lexicographic order among all possible outcomes.
Constraints indicate that n can be as large as 100,000, meaning a brute-force solution that examines all possible reversals explicitly would likely be too slow. The problem guarantees that the string is non-empty and contains only lowercase letters, which simplifies comparisons and eliminates the need to handle invalid characters. Edge cases could include strings where all characters are the same, strings already in sorted order, or strings of length 1.
Approaches
The brute-force approach would be to iterate over every possible k from 1 to n and perform both the prefix and suffix reversal for each k. For each reversed string, we would compare it to a running minimum to find the lexicographically smallest string. This approach is guaranteed to work because it exhaustively checks every valid transformation. However, it has a time complexity of O(n^2) since reversing a substring takes O(k) time and we do this for each possible k, making it impractical for large inputs.
The key insight for an optimal solution is to recognize that reversing a prefix or suffix essentially changes the order of the first or last few characters, and we are looking for the lexicographically smallest string. We only need to consider the position of the smallest character in the string relative to the first and last character, because reversing anything that doesn't include the smallest character at the front or end cannot produce a smaller string than moving the smallest character to the front. This insight allows us to limit the candidate reversals and evaluate only a linear number of options.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) | Check every prefix/suffix reversal |
| Optimal | O(n) | O(n) | Only evaluate reversals affecting positions that can yield a smaller string |
Algorithm Walkthrough
- Identify the smallest character in the string
s. This character will be a key target for moving to the front or end to potentially minimize the string lexicographically. - Generate candidate strings by considering reversals of prefixes and suffixes that include this smallest character. For each candidate, reverse the relevant substring (either the prefix up to the smallest character or the suffix from the smallest character to the end).
- Compare all candidate strings and keep track of the lexicographically smallest one.
- Return the smallest string after examining all relevant candidate reversals.
Why it works: This approach works because reversing any segment not containing the smallest character at a strategic position cannot produce a string smaller than the candidates considered. By focusing on positions that directly influence the start of the string, we avoid unnecessary computations while guaranteeing we find the global lexicographical minimum.
Python Solution
class Solution:
def lexSmallest(self, s: str) -> str:
n = len(s)
min_str = s
# Check prefix reversals
for k in range(1, n + 1):
candidate = s[:k][::-1] + s[k:]
if candidate < min_str:
min_str = candidate
# Check suffix reversals
for k in range(1, n + 1):
candidate = s[:n-k] + s[n-k:][::-1]
if candidate < min_str:
min_str = candidate
return min_str
This code iterates over all valid k values, performing the prefix and suffix reversals efficiently using Python slicing. Each candidate string is compared against the current minimum, ensuring the final result is the smallest possible.
Go Solution
func lexSmallest(s string) string {
n := len(s)
minStr := s
// Prefix reversals
for k := 1; k <= n; k++ {
prefix := reverse(s[:k])
candidate := prefix + s[k:]
if candidate < minStr {
minStr = candidate
}
}
// Suffix reversals
for k := 1; k <= n; k++ {
suffix := reverse(s[n-k:])
candidate := s[:n-k] + suffix
if candidate < minStr {
minStr = candidate
}
}
return minStr
}
func reverse(s string) string {
runes := []rune(s)
i, j := 0, len(runes)-1
for i < j {
runes[i], runes[j] = runes[j], runes[i]
i++
j--
}
return string(runes)
}
The Go implementation mirrors the Python approach, using a helper reverse function to reverse slices of the string. The candidate comparison uses Go's string lexicographical comparison.
Worked Examples
Example 1: s = "dcab"
| k | Prefix Reversal | Resulting String | Suffix Reversal | Resulting String |
|---|---|---|---|---|
| 1 | "d" | "dcab" | "b" | "dcab" |
| 2 | "cd" | "cdab" | "ab" | "dcba" |
| 3 | "acd" | "acdb" | "cab" | "dabc" |
| 4 | "bacd" | "bacd" | "dcab" | "bacd" |
Lexicographically smallest: "acdb"
Example 2: s = "abba"
| k | Prefix Reversal | Resulting String | Suffix Reversal | Resulting String |
|---|---|---|---|---|
| 1 | "a" | "abba" | "a" | "abba" |
| 2 | "ba" | "baba" | "ba" | "abba" |
| 3 | "bba" | "aabb" | "bba" | "abba" |
| 4 | "abba" | "abba" | "abba" | "abba" |
Lexicographically smallest: "aabb"
Example 3: s = "zxy"
| k | Prefix Reversal | Resulting String | Suffix Reversal | Resulting String |
|---|---|---|---|---|
| 1 | "z" | "zxy" | "y" | "zxy" |
| 2 | "xz" | "xzy" | "xy" | "zyx" |
| 3 | "yxz" | "yxz" | "zxy" | "xyz" |
Lexicographically smallest: "xzy"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n^2) | Each prefix/suffix reversal takes O(k), summed over n gives O(n^2) |
| Space | O(n) | Each candidate string requires O(n) space |
The quadratic time is acceptable for small examples but could be optimized further using advanced data structures like suffix arrays or rolling hashes to compare reversals without constructing strings explicitly.
Test Cases
# Basic examples
assert Solution().lexSmallest("dcab") == "acdb" # Example 1
assert Solution().lexSmallest("abba") == "aabb" # Example 2
assert Solution().lexSmallest("zxy") == "xzy" # Example 3
# Edge cases
assert Solution().lexSmallest("a") == "a" # Single character
assert Solution().lexSmallest("aa") == "aa" # All identical characters
assert Solution().lexSmallest("ba") == "ab" # Two characters, swap
assert Solution().lexSmallest("cba") == "abc" # Reverse entire string
assert Solution().lexSmallest("abcd") == "abcd" # Already smallest
| Test | Why |
|---|---|
| "dcab" | Standard prefix reversal example |
| "abba" | Standard suffix reversal example |
| "zxy" | Mixed characters, minimal reversal not at ends |
| "a" | Single character edge case |
| "aa" | Identical characters edge case |
| "ba" | Smallest swap to minimize |
| "cba" | Full reversal yields minimum |
| "abcd" | Already minimal, no operation improves |
Edge Cases
One important edge case is a single-character string. Since reversing a single character has no effect, the algorithm should correctly return the string itself. Another edge case is when all characters are identical. Any reversal does not change the string, so the minimum is trivially the string itself. Finally, strings that are already lexicographically sorted require careful handling; the algorithm should still perform exactly one reversal, even if it does not improve the string, to satisfy the problem's requirement of exactly one operation. Each of these scenarios is handled naturally by the algorithm through its exhaustive prefix and suffix reversal checks.