1.1
直接输出 S。 期望得分：5.
1.2
注意到将 S 通过操作变为另一个串最多只需要 次操作，因此直接将 S 中的字符排序后输出即可。 期望得分：5.
1.3 S 中仅包含 a, b 两种字符
既然是要字典序最小，容易想到从前往后按位贪心。设前 位的字符都已经确定，现在要确定第 i 位的字符。令 ，找到 中的第一个 a，设为 ，容易证明把 通过 次交换移到 是最优的。 因此每次暴力找到 ，将其移动到第 个位置，然后将 减去 ，直到所有位置都被确定为止。 时间复杂度 。期望得分：15.
1.4
同样考虑从前往后贪心。设前 位的字符都已经确定，令 ，找到 中的最小且尽量靠前的字符 ，将其移动到第 个位置，然后将 减去 ，直到所有位置都被确定为止。 时间复杂度 。期望得分：95.
1.5 正解
考虑如何优化上述贪心过程。注意到我们每次只需要找到区间的最小值，或是删掉某一个位置的字符。可以使用线段树或平衡树来实现。 时间复杂度 。期望得分：100