3038. 构造字典序最小字符串

单点时限: 2.0 sec

内存限制: 256 MB

给定长度为 N 的字符串 S,要构造一个长度为 N 的字符串 T。起初,T 是一个空串,随后反复执行下列两个操作中的任意一个,最终 目标是构造字典序尽可能小的字符串 T。

操作一:从 的头部取一个字符,加到 的尾部。

操作二:从 的尾部取一个字符,加到 的尾部。

例如:输入 ,S=ACDBCB;构造的 T=ABCBCD

具体按下图进行操作。

输入格式

第 1 行:整数 为问题数。

第 2 行:第一个 问题中的 ,表示字符串 的长度。

第 3 行:输入一个字符串 ,只包含大小写英文字母。

第 4 ~ 2*T+1 行:后面问题的数据 ,格式与第 1 个问题相同。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等),然后 输出由 S 字符串构造出来的 字典序尽可能小的字符串 T。

样例

Input
3
2
ba
5
SORTS
10
Sarumanarm
Output
case #0:
ab
case #1:
SORST
case #2:
Samranamru

673 人解决,785 人已尝试。

983 份提交通过,共有 2432 份提交。

1.3 EMB 奖励。

创建: 5 年,7 月前.

修改: 1 年,7 月前.

最后提交: 1 天,9 小时前.

来源: N/A

题目标签