問題文
你听说过字符串的字典顺序比较吗?如果你不知道 ABC007 B 问题 您可能需要阅读中的定义。
这次,我想让你解决一个问题,其中字典顺序起着重要作用。
一、小写字母(
仅a-z) N 字符串
可以通过重新排列 S 被给予。S = S_1,\,S_2,\,...,\,S_N 中的字符来创建的字符串
在 T = T_1,\,T_2,\,...,\,T_N 中,我希望你找到按字典顺序最小的那个。
然而,排序方法是 1 只有一个限制。单独的整数 给定 K ,计算位置相对于原始位置发生变化的字符数。 K 必须低于。换句话说,S_i ≠ T_i (字符不匹配) i (1 ≦ i ≦ N) 是数量 K 仅可以使用以下排序方法。
*这个问题比通常的ABC C问题更难。通过按下面的按钮,您可以阅读解决此问题的想法的解释作为提示。请慢慢来。
入力
输入将以以下形式从标准输入给出。
N K S
- 1 行是一个整数,表示字符串中的字符数。 N (1 ≦ N ≦ 100)和一个表示可重新定位的字符数上限的整数。 给出 K (0 ≦ K ≦ N)。
- 2 行仅包含小写字母 通过重新排列 N 字符串 可以通过重新排列 S 被给予。
出力
S 中的字符可以创建的字符串,其位置与原来相比发生变化的字符数为 K 按字典顺序查找小于或等于的最小字符串 1 行输出。
还在输出末尾包含换行符。
入力例1
3 2 abc
出力例1
abc
位置发生变化的字符数为 2 以下 ,所以你根本不需要做任何排序。
这种情况下,根本不排序是最小的。
入力例2
7 2 atcoder
出力例2
actoder
-
首先,T 的第一个字符
a(原始字符串atcoder(最小的字母表)。- 这次从原来 S 的第一个字符是
a,所以 它可以是T 的第一个字符a。 (例如,没有任何排序 S = T ,那么 您可以使用T 的第一个字符a来查看可以做什么 - 所以,T 的 1 第一个字母是
a被确定。
- 这次从原来 S 的第一个字符是
-
接下来,2 第一个字母
想想是否可以
c。 第一个- T 第一个 2 人物
ac,此时至少c已从原来的位置移动。 - 所以,S 的 3 字符之后
对于
coder,还 T 不使用字母 排列好deort并计算位置发生变化的字符数。 1 你需要思考下面是否可以这样做。 - 这次
排序
deort重新排列toder鉴于 T =actoder位置发生变化的字符数为 你可以摆脱 2 。 - 因此
其被确定为 2 第一个字母是
c。
- T 第一个 2 人物
-
接下来,3 第一个字母
想想是否可以
d。 第一个- T 第一个 3 人物
acd,那么此时c和d已从原来的位置移动。 - 所以,4 在第一个字符之后,字符不能从其原始位置进一步移动。
- 但是仍然
无论你如何安排 T 不使用字母
排列好
eort, 您无法完全匹配S 的 4 字符之后 对于oder。 它不能是 - 所以,3 第一个字母
想想是否可以
d。
- T 第一个 3 人物
-
d不起作用,所以3 在第一个字符上 考虑是否可以使用e。- 早些时候
与
d的情况一样, 它也不可能是3 第一个字母 想想是否可以e。
- 早些时候
与
-
e也失败了,所以 考虑是否可以使用3 在第一个字符上 考虑是否可以使用o。- ...
- ...
这样,从第一个字母开始,你能使用尚未使用过的字母中最小的字母吗?答案是按顺序尝试以下操作。
您可以到达 actoder 。
入力例3
7 7 atcoder
出力例3
acdeort
K = 7 因此您可以根据需要重新排列它们。正如问题文本中提到的,在这种情况下,您可以通过按字母顺序排列它们来创建最小的字符串。
入力例4
10 3 helloworld
出力例4
dehloworll