CF1624D Palindromes Coloring

给定一个由小写拉丁字母组成的字符串 $s$。 你可以将其中一些字母染成 $1$ 到 $k$ 的颜色。并不是所有字母都必须被染色。但对于每种颜色，必须至少有一个字母被染成该颜色。 然后，你可以任意多次交换被染成同一种颜色的任意两个字符。 之后，将会生成 $k$ 个字符串，第 $i$ 个字符串包含所有被染成第 $i$ 种颜色的字符，按照它们在原字符串 $s$ 中的顺序排列。 你的任务是给字符串中的字符染色，使得所有得到的 $k$ 个字符串都是回文串，并且这 $k$ 个字符串中最短的那个字符串的长度尽可能大。 如果需要澄清，请参考样例第一个测试点的说明。 回忆一下：如果一个字符串从左往右和从右往左读都是一样的，则称其为回文串。例如，字符串 abacaba、cccc、z 和 dxd 是回文串，而 abab 和 aaabaa 不是。

输入的第一行为一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。 接下来是每组测试数据的描述。 每组测试数据的第一行为两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$），分别表示字符串的长度和可用的颜色数。第二行为一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示可以得到的最短回文串的最大长度。

- 在第一个测试点中，$s$ = "bxyaxzay"，$k=2$。我们用 $1$ 到 $8$ 的下标表示字符串中的位置。以下染色方案可行：$\mathtt{\mathbf{\color{red}{b}\color{blue}{xy}\color{red}{a}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}$（字母 z 未被染色）。染色后： - 交换两个红色字符（下标 $1$ 和 $4$），得到 $\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}$； - 交换两个蓝色字符（下标 $5$ 和 $8$），得到 $\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{y}z\color{red}{a}\color{blue}{x}}}$。 现在，对于每种颜色，从左到右写出对应的字符，得到两个字符串 $\mathtt{\mathbf{\color{red}{aba}}}$ 和 $\mathtt{\mathbf{\color{blue}{xyyx}}}$。它们都是回文串，最短的长度为 $3$。可以证明，最短回文串的最大长度无法超过 $3$。 - 在第二个测试点中，以下染色方案可行：$[1, 1, 2, 2, 3, 3]$。无需交换字符。得到的字符串均为 aa，都是回文串，长度为 $2$。 - 在第三个测试点中，可以任意染色一个字符并取出来作为字符串。 - 在第四个测试点中，可以将第 $i$ 个字符染成第 $i$ 种颜色。 - 在第五个测试点中，可以每种颜色各染一个字符。 - 在第六个测试点中，以下染色方案可行：$[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0]$。重新排列字符，可以得到回文串 abcba 和 acbca。 由 ChatGPT 4.1 翻译