← 返回题目列表

Codeforces · 1799/C

C. 按字典顺序排列的最小值

中文机器翻译题面 查看原题

给你一个字符串 $$$s$$$。您可以对字符重新排序以形成字符串 $$$t$$$。将 $$$t_{\mathrm{max}}$$$ 定义为 $$$t$$$ 和 $$$t$$$ 按相反顺序的字典最大值。

给定 $$$s$$$,确定 $$$s$$$ 的所有重新排序 $$$t$$$ 中 $$$t_{\mathrm{max}}$$$ 按字典顺序排列的最小值。

当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:

- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含字符串 $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$)。 $$$s$$$ 仅由小写英文字母组成。

保证所有测试用例的 $$$|s|$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印 $$$t_{\mathrm{max}}$$$ 在 $$$s$$$ 的所有重新排序中按字典顺序排列的最小值 $$$t$$$。

示例

输入 #1

12
a
aab
abb
abc
aabb
aabbb
aaabb
abbb
abbbb
abbcc
eaga
ffcaba

输出 #1

a
aba
bab
bca
abba
abbba
ababa
bbab
bbabb
bbcca
agea
acffba

注意

对于第一个测试用例,$$$s$$$ 只有一次重新排序,即“a”。

对于第二个测试用例,$$$s$$$ 进行了 3 次重新排序。

- $$$t = \mathtt{aab}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa}$$$
- $$$t = \mathtt{aba}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba}$$$
- $$$t = \mathtt{baa}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa}$$$

所有情况下 $$$t_{\mathrm{max}}$$$ 的字典最小值是“aba”。