ACM-ICPC-OJ训练营

问题 2846 --后来者居上

2846: 后来者居上

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 3
[提交][状态][讨论版][命题人:]

题目描述

给你一个字符串s，你可以对该字符串精确地应用这个操作一次：选择索引i并将字符si移到字符串的开头（在旧的位置上将其删除）。例如，如果你将索引i=4的操作应用于从1开始编号的字符串 "abaacd"，你将得到字符串 "aabacd"。通过此操作可以得到的词典上最小†的字符串是什么？
当且仅当以下情况成立时，一个字符串a比相同长度的字符串b小：
在a和b不同的第一个位置，字符串a有一个字母在字母表中出现的时间比b中的相应字母早。

输入描述

每个测试包含多个测试用例。第一行包含测试用例的数量t（1≤t≤10^4）。测试用例的描述如下。
每个测试用例的第一行包含一个整数n（1≤n≤10^5）--字符串的长度。
每个测试案例的第二行包含长度为n的字符串s，由小写英文字母组成。
保证所有测试用例的n之和不超过10^5。

输出描述

对于每个测试用例，在单独的一行中打印出对原始字符串精确操作一次后可以得到的词汇学上最小的字符串。

样例输入

4
3
cba
4
acac
5
abbcb
4
aaba

样例输出

acb
aacc
abbcb
aaab

提示

在第一个测试案例中，你需要将最后一个字符移到开头。

在第二种情况下，你需要移动第二个字母 "a"。

在第三组中，你需要应用i=1的操作，那么字符串将不会改变。

来源

22计3欧阳齐

[提交][状态]