問題文

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

入力例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