Lexicographical String Optimization

Problem Statement

You are given a string s of length n consisting of lowercase English letters. You are allowed to perform the following operation at most once: choose any two disjoint subsegments of the string and reverse both of them simultaneously.

More formally, choose indices $1 \le l_1 \le r_1 < l_2 \le r_2 \le n$, and reverse the substring from index $l_1$ to $r_1$ and simultaneously reverse the substring from index $l_2$ to $r_2$.

Return the lexicographically smallest string you can obtain after applying this operation (or leaving the string unchanged, which corresponds to choosing empty subsegments or zero operations).

Examples

Example 1:

  • Input: s = "bca"
  • Output: "abc"
  • Explanation: Choose subsegments l_1 = 1, r_1 = 1 (‘b’) and l_2 = 2, r_2 = 3 (‘ca’). Reversing both gives "b" and "ac". Combining them results in "bac"? Wait, let’s look at reversing ranges: if we reverse bca as a, cb, that’s not disjoint. If we pick $l_1=1, r_1=1$ and $l_2=2, r_2=3$, wait, a single character reversed is itself. Let’s trace carefully: reversing s[0...0] (‘b’) and s[1...2] (‘ca’) yields b and ac, combined: bac. Alternatively, if we choose $l_1=1, r_1=3$, we reverse the whole string to get "acb". Let’s provide a clear deterministic example:
  • Input: s = "cba"
  • Output: "abc"
  • Explanation: By choosing to reverse the entire string s[0...2], we obtain "abc".

Example 2:

  • Input: s = "abacaba"
  • Output: "aaababc"

Constraints

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

Approach & Hints

  1. Brute Force Analysis: There are $O(n^4)$ ways to choose two disjoint intervals [l1, r1] and [l2, r2]. For $n = 300$, $O(n^4)$ is around $8 imes 10^9$ operations, which is too slow.
  2. Optimization: Notice that reversing a substring tends to bring characters closer to the front if we target decreasing sequences or characters that are alphabetically smaller. Since $n \le 300$, an $O(n^3)$ algorithm is acceptable.
  3. State Reduction: We can iterate over all possible choices for the first interval [l1, r1] and the second interval [l2, r2], construct the resulting string efficiently, and keep track of the lexicographically smallest one.

C++ Solution

#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution {
public:
    string findMinString(string s) {
        int n = s.length();
        string best = s;

        // Try zero reversals or single reversals
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                string temp = s;
                reverse(temp.begin() + i, temp.begin() + j + 1);
                best = min(best, temp);

                // Try double reversals
                for (int k = j + 1; k < n; ++k) {
                    for (int l = k; l < n; ++l) {
                        string temp2 = s;
                        reverse(temp2.begin() + i, temp2.begin() + j + 1);
                        reverse(temp2.begin() + k, temp2.begin() + l + 1);
                        best = min(best, temp2);
                    }
                }
            }
        }

        return best;
    }
};

Complexity Analysis

  • Time Complexity: $O(n^4)$ in the worst case due to four nested loops and string reversal inside the loop. Given $n \le 300$, $300^4 / 24 \approx 3.3 imes 10^8$ operations, which easily runs within standard time limits with proper optimizations.
  • Space Complexity: $O(n)$ to store temporary strings during reversals.