CF1799C Double Lexicographically Minimum

给定一个字符串 $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$ 的 $t_{\mathrm{max}}$ 的字典序最小值。

对于第一个测试用例，$s$ 只有一种重排方式，即 "a"。 对于第二个测试用例，$s$ 有三种重排方式： - $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"。 由 ChatGPT 4.1 翻译