P9458 [Beginner Contest #14] Fusu and Strings (Hard Version)

As everyone knows, the string problems in the monthly Beginner Contest are all ideas enumerated by Fusu.

Given a 01 string $s$, you may choose any non-empty substring of $s$ and **reverse** this substring once within $s$. What is the lexicographically smallest string you can obtain? Formally, you can choose an interval $[l, r]$ satisfying $1 \leq l \leq r \leq |s|$, and construct a string $t$ such that: $$t_i = \begin{cases}s_i, &i < l \text{ or } i > r \\ s_{r - (i - l)}, & l \leq i \leq r\end{cases}$$ Minimize the lexicographic order of string $t$.

The input contains only one line with a string, representing $s$.

Output one line with a string, representing the lexicographically smallest string that can be obtained.

### Explanation for Sample 1 $s = \texttt{\underline{10}1}$. Reverse the underlined substring to get $t = \texttt{011}$. ### Explanation for Sample 2 $s = \texttt{00\underline{10100}}$. Reverse the underlined substring to get $\texttt{0000101}$. ### Constraints Let $|s|$ denote the length of the input string. - For $100\%$ of the testdata, $1 \leq |s| \leq 3000$. $s$ contains only characters $\texttt{0,1}$. Translated by ChatGPT 5