(function() { ("#hint").on("click", function() { $(this).next().slideDown(); }); });

問題文

文字列の辞書式順序による比較についてはご存知だろうか？知らない場合は 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 問題に比べ難しくなっています。下のボタンを押すことで、ヒントとしてこの問題を解くためのアイデアの説明を読むことができます。じっくり取り組んでみてください。

ヒントを表示する

重要な点は、辞書順で最小を目指すときには 文字列の先頭にできるだけ小さいアルファベットがある方がよい ということです。なので、まずは $T$ の $1$ 文字目をできるだけ小さいアルファベットにすることを考えましょう。

$S$ の文字のうち、小さいアルファベットから順に $T$ の先頭にできるかを試していって、最初にできるとわかった文字が $T$ の $1$ 文字目として決まります。次は残った文字のうち小さいものから順に $T$ の $2$ 文字目にできるか試していき、$3$ 文字目、$4$ 文字目と同様に決めていきます（入出力例2 でもう少し具体的な説明をしています）。

試すときに必要なのは「$T$ をある文字列 $t$ で始めることができるか？」を判定することです。これは、$S$ のうちまだ $t$ で使っていない文字をうまく並び替えて、$S$ の後ろのほうとの文字の不一致の数をできるだけ少なくし、全体として不一致の数を $K$ 以下にできるかどうかで判定できます。

たとえば $S =$ program、$K = 3$ で、$T$ の最初 $3$ 文字を aro にできるかを判定したいとします。このとき、すでに aro と $S$ の先頭 $3$ 文字 pro で不一致が $1$ つあるので、残りの部分で不一致の数を $2$ 以下にしないといけません。つまり、まだ使っていない文字 pgrm をうまく並び替えて、$S$ の後ろのほうである gram との不一致の数をできるだけ減らして $2$ 以下にできれば OK です。

この方法と、判定の部分を具体的にどうプログラムにするかについては自力で頑張ってみましょう。

---

入力

入力は以下の形式で標準入力から与えられる。

$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 に決まります。
• 次に、$2$ 文字目を c にできるかについて考えます。
  • $T$ の最初の $2$ 文字が ac であるとすると、この時点で少なくとも c は元の位置から場所が変わっています。
  • なので、$S$ の $3$ 文字目以降である coder に対して、まだ $T$ に使っていないアルファベット deort をうまく並べて、位置の変わった文字の個数を $1$ 以下にできるかどうかを考える必要があります。
  • 今回は deort を並び替えて toder とすれば $T =$ actoder となって、位置の変わった文字の個数が $2$ で済ませられます。
  • よって $2$ 文字目が c と決まります。
• 次に、$3$ 文字目を d にできるかについて考えます。
  • $T$ の最初の $3$ 文字が acd であるとすると、この時点で c と d は元の位置から場所が変わっています。
  • なので、$4$ 文字目以降ではこれ以上元の位置から文字を動かしてはいけないことになります。
  • しかし、まだ $T$ に使っていないアルファベット eort をどのように並べても、$S$ の $4$ 文字目以降である oder とぴったり一致させることはできません。
  • なので、$3$ 文字目を d にすることはできません。
• d がだめだったので、$3$ 文字目に e を使えるかを考えます。
  • さきほどの d の場合と同じように、$3$ 文字目を e にすることもできません。
• e もだめだったので、$3$ 文字目に o が使えるかを考えます。
  • ...
• ...

このようにして最初の文字から順に、まだ使っていない文字のなかで最も小さいアルファベットが使えるかどうか？を順に試していくことで答えである actoder に辿り着くことができます。

---

入力例3

7 7
atcoder

出力例3

acdeort

$K = 7$ なので、好きなように並び替えをして構いません。問題文にもあるように、この場合はアルファベット順に並べることで最小の文字列を作ることができます。

---

入力例4

10 3
helloworld

出力例4

dehloworll

---