Introduction

In the realm of string manipulation, one interesting problem is finding the lexicographically smallest string by reversing exactly one contiguous substring. This problem has applications in genetic data analysis, text processing, and competitive programming. The goal is to determine the smallest possible string achievable through a single reversal operation.

Understanding Lexicographical Order

Lexicographical order is the generalization of dictionary order to strings. Given two strings s1 and s2, s1 is lexicographically smaller than s2 if, at the first position where they differ, the character in s1 comes before the character in s2 alphabetically.

For example:

• "abc" is smaller than "abd" (differ at position 2: 'c' < 'd')
• "a" is smaller than "aa" (first string is a prefix, and shorter)

Problem Statement

Given a string, find the smallest possible string by reversing exactly one of its substrings. A substring is a contiguous sequence of characters. Note that reversing a substring of length 1 (or length 0) effectively means "no change," so the original string is always a valid candidate.

Brute Force Solution

The straightforward approach considers all possible substrings:

1. For each pair of indices $(i, j)$ where $0 \leq i < j \leq n$, reverse the substring from index $i$ to $j$.
2. Compare the resulting string with the current minimum.
3. Return the smallest string found.

1def find_lexicographically_smallest(s):
2    min_string = s
3    n = len(s)
4
5    for i in range(n):
6        for j in range(i + 1, n):
7            reversed_substring = s[i:j+1][::-1]
8            new_string = s[:i] + reversed_substring + s[j+1:]
9            if new_string < min_string:
10                min_string = new_string
11
12    return min_string

Complexity

• Time: $O(n^3)$, because there are $O(n^2)$ pairs and each string comparison/reversal takes $O(n)$.
• Space: $O(n)$ for storing the reversed string.

Optimized Approach

The brute force is impractical for large strings. A key observation enables a much faster solution:

Observation: To minimize the string lexicographically, you want the smallest possible character as early as possible. The optimal reversal must bring a smaller character to an earlier position.

Greedy Algorithm

1. Scan left to right. Find the first position $i$ where $s[i]$ is not the smallest character in $s[i:]$.
2. Find the rightmost occurrence of the smallest character in $s[i:]$. Call this position $j$.
3. Reverse $s[i..j]$.

This works because the reversal brings the smallest available character to the earliest "imperfect" position, and taking the rightmost occurrence ensures that if there are ties, the characters between $i$ and $j$ are sorted in the best possible order after reversal.

1def find_smallest_optimized(s):
2    s = list(s)
3    n = len(s)
4
5    for i in range(n):
6        min_char = min(s[i:])
7        if s[i] != min_char:
8            # Find rightmost occurrence of min_char
9            j = n - 1
10            while s[j] != min_char:
11                j -= 1
12            # Reverse s[i..j]
13            s[i:j+1] = s[i:j+1][::-1]
14            break
15
16    return ''.join(s)

This runs in $O(n)$ for finding the optimal reversal point, plus $O(n)$ for the reversal itself, giving $O(n)$ overall.

Worked Example

Original string: "cab"

Brute force enumeration:

The smallest result is "acb", achieved by reversing indices (0, 1).

Greedy approach: At position 0, the smallest character in "cab" is 'a' at index 1. Reverse s[0..1] to get "acb". Same answer, found in one scan.

Edge Cases

• Already sorted: If the string is already the lexicographically smallest (e.g., "abc"), no reversal improves it.
• All identical characters: Any reversal produces the same string, so the original is returned.
• Single character: The string is already minimal.

Summary

Finding the lexicographically smallest string by reversing a substring comes down to identifying where the string first deviates from sorted order and reversing just enough to bring the smallest available character forward. The greedy approach achieves this in linear time, making it practical for large inputs.