← 返回题目列表

Codeforces · 1530/E

E. 极小极大

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

字符串 $$$t = t_1 t_2 \ldots t_n$$$ 及其位置 $$$i$$$ 的前缀函数定义为子串 $$$t_1 t_2 \ldots t_i$$$ 的最长真(不等于整个子串)前缀的长度 $$$k$$$,它也是同一子串的后缀。

例如,对于字符串 $$$t = $$$ abacaba,位置 $$$1, 2, \ldots, 7$$$ 中的前缀函数的值等于 $$$[0, 0, 1, 0, 1, 2, 3]$$$。

令 $$$f(t)$$$ 等于字符串 $$$t$$$ 在其所有位置上的前缀函数的最大值。例如,$$$f($$$abacaba$$$) = 3$$$。

给你一个字符串 $$$s$$$。对其字符任意重新排序,得到字符串$$$t$$$(字符串$$$s$$$和$$$t$$$中任意字符出现的次数必须相等)。 $$$f(t)$$$ 的值必须最小化。在最小化 $$$f(t)$$$ 的所有选项中,选择字符串 $$$t$$$ 按字典顺序最小的选项。

输入

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

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

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

输出

对于每个测试用例,打印一个字符串 $$$t$$$。

字符串 $$$s$$$ 和 $$$t$$$ 中的多组字母必须相等。 $$$f(t)$$$ 的值(字符串 $$$t$$$ 中前缀函数的最大值)必须尽可能小。字符串 $$$t$$$ 必须是满足前面条件的所有字符串中按字典顺序最小的字符串。

示例

输入 #1

3
vkcup
abababa
zzzzzz

输出 #1

ckpuv
aababab
zzzzzz

注意

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

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

在第一个测试用例中,$$$f(t) = 0$$$ 并且前缀函数的值为 $$$[0, 0, 0, 0, 0]$$$ 对于任何字母排列。字符串 ckpuv 是字符串 vkcup 的字母按字典顺序排列的最小排列。

在第二个测试用例中,$$$f(t) = 1$$$,前缀函数的值为$$$[0, 1, 0, 1, 0, 1, 0]$$$。

在第三个测试用例中,$$$f(t) = 5$$$,前缀函数的值为$$$[0, 1, 2, 3, 4, 5]$$$。