AT_abc009_3 [ABC009C] 辞書式順序ふたたび

你知道字符串的字典序比较吗？如果不知道，可以阅读 [ABC007 的 B 问题](http://abc007.contest.atcoder.jp/tasks/abc007_2) 中的定义。 这次，你需要解决一个与字典序有关的问题。 首先，给定一个仅由小写英文字母（`a-z`）组成的长度为 $N$ 的字符串 $S$。请你在将 $S = S_1, S_2, ..., S_N$ 的字符重新排列后，构造出一个字符串 $T = T_1, T_2, ..., T_N$，使得 $T$ 在所有可以通过重新排列 $S$ 得到的字符串中，字典序最小。 不过，排列方式有一个限制。给定一个整数 $K$，要求原本位置发生变化的字符个数不能超过 $K$。也就是说，满足 $S_i \neq T_i$ 的 $i$（$1 \leq i \leq N$）的个数不能超过 $K$。 **注意：本题比通常的 ABC C 题更难。你可以点击下方按钮查看解题思路提示，建议你认真思考后再查看。** ::::info[显示提示] 在追求字典序最小时，**让字符串的前面尽可能出现较小的字母是有利的**。因此，首先考虑能否将 $T$ 的第一个字符设为尽可能小的字母。 依次尝试将 $S$ 中较小的字母放在 $T$ 的开头，找到第一个可行的字母后，将其作为 $T$ 的第一个字符。接着，在剩下的字符中，依次尝试将较小的字母放在 $T$ 的第二个字符位置，第三个、第四个字符同理确定（在样例 2 的解释中有更具体的说明）。 在尝试时，需要判断“能否让 $T$ 以某个字符串 $t$ 开头”。具体来说，就是判断能否用 $S$ 中还未使用的字符，通过合理排列，使得与 $S$ 后面部分的字符不一致的个数尽量少，并且总的不一致个数不超过 $K$。 例如，$S = $`program`，$K = 3$，现在想判断 $T$ 的前 $3$ 个字符能否为 `aro`。此时，`aro` 与 $S$ 的前 $3$ 个字符 `pro` 有 $1$ 个不一致，因此剩下部分的不一致个数必须不超过 $2$。也就是说，需要将还未用过的字符 `pgrm` 重新排列，使得与 $S$ 的后半部分 `gram` 的不一致个数尽量少，并且不超过 $2$，如果可以做到，则可行。 具体实现该方法以及判定部分的编程细节，请自行思考。 ::::

输入按以下格式从标准输入读入。 > $N$ $K$ > $S$ - 第 $1$ 行包含两个整数 $N$（字符串长度，$1 \leq N \leq 100$）和 $K$（允许改变位置的字符数上限，$0 \leq K \leq N$）。 - 第 $2$ 行包含一个仅由小写英文字母组成的长度为 $N$ 的字符串 $S$。

请输出通过重新排列 $S$ 得到的、且原本位置发生变化的字符个数不超过 $K$ 的所有字符串中，字典序最小的字符串 $T$。输出后需换行。

### 样例解释 1 由于允许改变位置的字符数最多为 $2$，所以完全不进行排列也是可以的。在本例中，不进行任何排列得到的字符串就是字典序最小的。 ### 样例解释 2 - 首先，考虑能否将 $T$ 的第一个字符设为 `a`（原字符串 `atcoder` 中最小的字母）。 - 这次 $S$ 的第一个字符本身就是 `a`，因此可以将 $T$ 的第一个字符设为 `a`。（例如完全不排列，$S = T$，此时 $T$ 的第一个字符就是 `a`） - 因此，$T$ 的第 $1$ 个字符确定为 `a`。 - 接着，考虑能否将第 $2$ 个字符设为 `c`。 - 若 $T$ 的前两个字符为 `ac`，此时至少 `c` 的位置发生了变化。 - 因此，需要判断能否用还未使用的字母 `deort` 重新排列，使得与 $S$ 的第 $3$ 个字符及之后的 `coder` 匹配时，位置变化的字符数不超过 $1$。 - 这次可以将 `deort` 排列为 `toder`，得到 $T = $`actoder`，此时位置变化的字符数为 $2$。 - 因此，第 $2$ 个字符确定为 `c`。 - 接着，考虑能否将第 $3$ 个字符设为 `d`。 - 若 $T$ 的前 $3$ 个字符为 `acd`，此时 `c` 和 `d` 的位置都发生了变化。 - 因此，$T$ 的第 $4$ 个及之后的字符不能再有位置变化。 - 但无论如何排列剩下的 `eort`，都无法与 $S$ 的 `oder` 完全一致。 - 因此，第 $3$ 个字符不能为 `d`。 - 依次尝试 `e`、`o` 等，最终可以确定答案为 `actoder`。 ### 样例解释 3 由于 $K = 7$，可以任意排列。此时，将所有字母按字母顺序排列即可得到字典序最小的字符串。 由 ChatGPT 4.1 翻译