CF1975H 378QAQ and Core

378QAQ 有一个长度为 $n$ 的字符串 $s$。定义一个字符串的“核心”为其字典序最大的子串$^\dagger$。 例如，"bazoka" 的核心是 "zoka"，"aaa" 的核心是 "aaa"。 378QAQ 想要重新排列字符串 $s$，使得其核心的字典序最小。请你找出所有 $s$ 的重排中，核心字典序最小的方案。 $^\dagger$ 字符串 $s$ 的子串是 $s$ 中一段连续的字母。例如，"defor"、"code" 和 "o" 都是 "codeforces" 的子串，而 "codes" 和 "aaa" 不是。 $^\ddagger$ 如果字符串 $p$ 满足以下任一条件，则称 $p$ 的字典序小于 $q$： - $p$ 是 $q$ 的前缀，且 $p \ne q$； - 在 $p$ 和 $q$ 第一个不同的位置，$p$ 的该字符的 ASCII 码小于 $q$ 的对应字符。 例如，"code" 和 "coda" 的字典序都小于 "codeforces"，而 "codeforceston" 和 "z" 则不是。

每个测试包含多组测试数据。第一行包含测试用例数 $t$（$1\leq t\leq 10^5$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$1\leq n\leq 10^6$），表示字符串 $s$ 的长度。 接下来一行包含一个长度为 $n$ 的字符串 $s$，仅包含小写英文字母。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每组测试数据，输出所有重排方案中核心字典序最小的结果。

在第一个测试用例中，所有可能的重排及其对应的核心如下： - "qaq"，其核心为 "qaq"。 - "aqq"，其核心为 "qq"。 - "qqa"，其核心为 "qqa"。 因此，所有重排方案中核心字典序最小的是 "qaq"。 由 ChatGPT 4.1 翻译