ARC140 A-Right String - くすと日記

文字列Tの先頭の文字を末尾に移動することを繰り返して作れる文字列の種類をf(T)とする。

文字列SのK文字以下の文字を変更した後のf(S)としてあり得る最小値を求める。

1 <= N <= 2000

0 <= K <= N

先頭の文字を削除して末尾に追加することをシフトすると呼ぶことにします。

長さNの完全にデタラメな文字列Tをシフトしていくと、シフトするたびに新しい文字列となり、N回シフトすると一周してもとの文字列に戻ります。よってf(T) = Nです。

f(T)を小さくするには、一周する前に元の文字列になればよいことになります。

例えば、T = "ABCABCABCABC" のとき、3回シフトすると元の文字列と同じになり、それ以降は今までに現れた文字列にしかならないので、f(T) = 3です。

この問題は、↓ができれば解けることになります。

文字列SをK文字まで置き換えて、できるだけ短い文字列を繰り返した文字列にする。

繰り返し単位となる文字列の長さは、Nの約数である必要があるので、Nの約数を小さい順に見ていき、その長さの文字列の繰り返しを作ることができるかどうか調べていきます。

例として、次のようなSを長さ2の文字列の繰り返しにするには、何文字置き換えればよいか考えます。

S = "ABAACC"

見やすいように2文字ごとに改行します。

ここで、各列について、その列を構成する文字がすべて同じになればよいです。

左から1番目の列は[A, A, C]なので、CをAに変えれば全てAになります(操作1回)。

左から2番目の列は[B, A, C]なので、いずれか1文字に他の2文字を合わせればよいです（操作2回）。

一般には、行数 - 列内で最も多く現れる文字の個数 でその列に必要な操作回数がわかります。

この例では合計3回の操作が必要になります。

必要な操作回数がK以下であれば、その繰り返し文字列を作ることができ、繰り返し単位の長さが回答になります。