CF940C Phone Numbers

电话号码在哪里？ 给定一个由小写英文字母组成的字符串 $s$ 和一个整数 $k$。请你找到一个长度为 $k$ 的字典序最小的字符串 $t$，满足 $t$ 的字母集合是 $s$ 的字母集合的子集，并且 $s$ 的字典序小于 $t$。 保证一定存在满足条件的答案。 注意，字母集合是集合而不是多重集。例如，abadaba 的字母集合为 $\{a, b, d\}$。 如果字符串 $p$ 是字符串 $q$ 的前缀且 $p \neq q$，或者存在某个 $i$ 使得 $p_i < q_i$ 且对于所有 $j < i$ 都有 $p_j = q_j$，那么字符串 $p$ 的字典序小于字符串 $q$。例如，abc 的字典序小于 abcd，abd 的字典序小于 abec，afa 的字典序不小于 ab，a 的字典序不小于 a。

输入的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \leq n, k \leq 100000$），分别表示 $s$ 的长度和 $t$ 的要求长度。 输入的第二行包含一个长度为 $n$ 的仅由小写英文字母组成的字符串 $s$。

输出满足要求的字符串 $t$。 保证一定存在满足条件的答案。

在第一个样例中，所有长度为 3，且字母集合是 $s$ 的字母集合的子集的字符串 $t$ 有：aaa，aab，aac，aba，abb，abc，aca，acb，……。其中，字典序大于 abc 的有：aca，acb，……。这些字符串中字典序最小的是 aca。 由 ChatGPT 4.1 翻译