LeetCode 3722 - Lexicographically Smallest String After Reverse

Difficulty: 🟡 Medium
Topics: Two Pointers, Binary Search, Enumeration

Solution

Problem Understanding

The problem asks us to find the lexicographically smallest string after performing exactly one reverse operation on a contiguous prefix or suffix of a given string s. The string consists only of lowercase English letters and can have a length up to 1000 characters.

In other words, we can either reverse the first k characters or the last k characters, for any valid k from 1 to n, and after performing this single operation, we want the string to be as small as possible in dictionary order. Lexicographical comparison is similar to comparing words in a dictionary: for example, "abc" is smaller than "acb" because 'b' < 'c' at the first differing character.

Key points from the problem:

The operation is mandatory and exactly once.
k can be any value from 1 to n.
The reversal can occur at the beginning or end of the string.
The string length is reasonable (n <= 1000), which allows for an O(n^2) approach if needed, but an optimized O(n) approach is preferable.

Important edge cases to consider:

Strings that are already sorted in ascending order. The operation may still change the string, so we must ensure the output is minimal after one reversal.
Strings with repeated characters.
Strings of length 1 (trivial reversal).

Approaches

Brute Force Approach:

The brute-force solution iterates over all possible k values from 1 to n, and for each k, reverses the first k characters and separately reverses the last k characters. We keep track of the lexicographically smallest string seen. This approach is correct because it exhaustively considers all allowed operations, but it is slow, with a time complexity of O(n^2) due to repeated string slicing and reversal.

Optimal Approach Insight:

We can leverage the fact that reversing a prefix or suffix is effectively changing the order of a substring. The key insight is that we only need to check reversals that start with a character smaller than the current first character or end with a character smaller than the last character, because only these can potentially decrease the lexicographical value. By iterating through the string and constructing candidate strings efficiently, we can reduce unnecessary comparisons.

We still need to check each candidate, but string concatenation in Python or Go is efficient enough that an O(n^2) implementation works comfortably for n <= 1000. However, the early pruning based on minimal first or last character can reduce the number of actual candidates considered.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Try all k from 1 to n for both prefix and suffix reversals
Optimal	O(n^2) worst case, O(n) average with pruning	O(n)	Generate candidates by reversing prefix or suffix intelligently, keep minimal

Algorithm Walkthrough

Initialize min_str to the original string s.
Iterate k from 1 to n:
Reverse the first k characters and concatenate with the remaining suffix to form a candidate string. Compare it with min_str and update if smaller.
Reverse the last k characters and concatenate with the remaining prefix to form another candidate string. Compare it with min_str and update if smaller.
Return min_str.

Why it works:

By iterating over all valid k and considering both prefix and suffix reversals, we guarantee that all possible outcomes of exactly one reversal are evaluated. Comparing each candidate ensures that the lexicographically smallest string is found.

Python Solution

class Solution:
    def lexSmallest(self, s: str) -> str:
        n = len(s)
        min_str = s
        
        for k in range(1, n + 1):
            # Reverse first k characters
            candidate_prefix = s[:k][::-1] + s[k:]
            if candidate_prefix < min_str:
                min_str = candidate_prefix
            
            # Reverse last k characters
            candidate_suffix = s[:n-k] + s[n-k:][::-1]
            if candidate_suffix < min_str:
                min_str = candidate_suffix
        
        return min_str

In this implementation, we systematically generate candidate strings by reversing the first or last k characters. The slicing operations s[:k][::-1] and s[n-k:][::-1] efficiently reverse the required substring. Updating min_str ensures that at the end of the loop, we have the lexicographically smallest result.

Go Solution

func lexSmallest(s string) string {
    n := len(s)
    minStr := s
    
    for k := 1; k <= n; k++ {
        // Reverse first k characters
        prefix := reverse(s[:k]) + s[k:]
        if prefix < minStr {
            minStr = prefix
        }
        
        // Reverse last k characters
        suffix := s[:n-k] + reverse(s[n-k:])
        if suffix < minStr {
            minStr = suffix
        }
    }
    
    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)
}

In Go, we convert the string to a []rune to handle character reversal correctly. The helper function reverse reverses the slice in place. The main function generates prefix and suffix reversal candidates and updates the minimal string accordingly.

Worked Examples

Example 1: "dcab"

k	Reverse Prefix	Reverse Suffix	Min So Far
1	"dcab"	"dcab"	"dcab"
2	"cdab"	"dcab"	"cdab"
3	"acd" + "b" = "acdb"	"dca" + "b" = "dabc"	"acdb"
4	"bacd"	"bacd"	"acdb"

Output: "acdb"

Example 2: "abba"

k	Reverse Prefix	Reverse Suffix	Min So Far
1	"abba"	"abba"	"abba"
2	"baba"	"aabb"	"aabb"
3	"bba" + "a" = "bbaa"	"abb" + "a" = "abba"	"aabb"
4	"abba"	"abba"	"aabb"

Output: "aabb"

Example 3: "zxy"

k	Reverse Prefix	Reverse Suffix	Min So Far
1	"zxy"	"zxy"	"zxy"
2	"xz" + "y" = "xzy"	"z" + "yx" = "zyx"	"xzy"
3	"yxz"	"yxz"	"xzy"

Output: "xzy"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	For each k (1 to n), we reverse a substring of up to n characters, so O(n^2) in total
Space	O(n)	Each candidate string requires O(n) space

Even though the worst case is O(n^2), with n <= 1000 this is acceptable.

Test Cases

# Provided 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"  # two identical characters
assert Solution().lexSmallest("ba") == "ab"  # two characters, needs reversal
assert Solution().lexSmallest("cba") == "acb"  # full reversal of first 2 is optimal
assert Solution().lexSmallest("abc") == "bac"  # operation must be performed even if already sorted

Test	Why
"dcab"	Normal case with both prefix and suffix reversals possible
"abba"	Reversal of suffix produces smallest string
"zxy"	Small string with first reversal optimal
"a"	Single character edge case
"aa"	Identical characters, reversal has no effect
"ba"	Two characters needing reversal
"cba"	Optimal reversal is partial prefix
"abc"	Already sorted string, operation still required

Edge Cases

Single Character: For s = "a", any reversal does not change the string. The algorithm correctly