CF1530E Minimax

字符串 $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$。 字符串 $t$ 必须与 $s$ 为同一个多重集合（即每个字符出现次数相同）。$t$ 的前缀函数最大值 $f(t)$ 要尽可能小。在所有满足条件的 $t$ 中，输出字典序最小的一个。

如果字符串 $a$ 是字符串 $b$ 的前缀，且 $a \ne b$，则 $a$ 的字典序小于 $b$。或者，在 $a$ 和 $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]$。 由 ChatGPT 4.1 翻译