#1785. [语言月赛 202307] 扶苏和串

[语言月赛 202307] 扶苏和串

题目描述

给定一个 01 字符串 ss,你可以任选 ss 的一个非空子串,把这个子串在 ss 中翻转一次。

问你能得到字典序最小的字符串是什么?

形式化的,你可以选择一个区间 [l,r][l, r] 满足 1≤l≤r≤∣s∣1 \leq l \leq r \leq |s|,构造一个串 tt 满足:

$$t_i = \begin{cases}s_i, &i < l \text{ 或 } i > r \\ s_{r - (i - l)}, & l \leq i \leq r\end{cases}$$

这里字符串的下标从 11 开始。

最小化字符串 tt 的字典序。

输入格式

输入只有一行一个字符串,表示 ss。

输出格式

输出一行一个字符串,表示得到的字典序最小的字符串。

样例

101
011
0010100
0000101

题目来源:洛谷 B3810