SP7103 EDDIST - Edit Distance

两个字符串 $S$ 和 $T$ 的编辑距离是指将字符串 $S$ 转换为字符串 $T$ 所需的最少编辑操作次数。可以进行的编辑操作有： - 在任意位置插入一个字符 - 修改一个已存在的字符 - 删除一个已存在的字符 例如，「pantera」和「aorta」的编辑距离是 5，因为以下修改步骤是有效的且没有更短的可能： 1. 「pantera」变为「antera」 2. 「antera」变为「aotera」 3. 「aotera」变为「aoera」 4. 「aoera」变为「aora」 5. 「aora」变为「aorta」 在这个问题中，给定一个整数 $K$ 和一个字符串 $S$，我们需要构造一个字符串 $T$，使其与 $S$ 的编辑距离不超过 $K$。在可能的字符串中，我们需要选择字典序最小的那个字符串 $T$。在字典序中，一个字符串总是排在它的任何真前缀之后。对于两个不互为前缀的字符串，从左至右找到第一个不同字符时，字母靠前的字符串字典序更小。注意，空字符串（长度为零）也是有效字符串，在字典序上排在任何非空字符串之前。

输入包含若干测试用例。每个测试用例在一行中给出，包括一个整数 $K$（$0 \le K \le 1000$）和一个仅由小写字母组成的字符串 $S$，两者之间用一个空格分隔。输入的最后一行为“-1 *”，代表结束，不作为测试用例处理。

对于每个测试用例，输出一个由小写字母组成的字符串 $T$，使得其与 $S$ 的编辑距离不超过 $K$。若有多个符合条件的字符串，请输出字典序最小的那个。 **本翻译由 AI 自动生成**