题解

思路

一次操作等价于不断选取当前区间内的一对位置 $p<q$ 交换，随后只在 $(p,q)$ 内继续选择。

做法

因此从左到右贪心：对当前左端 $l$，若剩余区间中存在比 $s_l$ 小的字符，就选其中字符值最小且位置最靠右的一个与 $s_l$ 交换，并把右端缩到该位置左侧；否则直接跳过 $l$。最小字符保证当前位置最优，在字符相同时选择最右位置会给后续保留最大的可选区间，所以该贪心逐位得到全局字典序最小解。

为每种小写字母保存其所有出现位置。每个左端依次检查至多 $26$ 种字符，并在位置表中二分找到不超过当前右端的最右位置；交换过的两个位置都会立刻离开后续区间，因此无需更新位置表。

复杂度

时间复杂度为 $O(26N)$，空间复杂度为 $O(N)$。