JJOOII 2 (JJOOII 2)

ビ太郎は友人のビバ子から誕生日プレゼントにJ, O, I の3 種類の文字からなる長さN の文字列S をも
らった.
K を1 以上の整数とする.K 個の文字J,K 個の文字O,K 個の文字I をこの順に並べた文字列をレベ
ルK のJOI 文字列と呼ぶことにする.例えば,JJOOII はレベル2 のJOI 文字列である.
ビ太郎はレベルK のJOI 文字列が好きなので,以下の3 種類の操作を任意の回数,任意の順番で行うこ
とで,文字列S をレベルK のJOI 文字列に変換することにした.
操作1 文字列S の先頭の文字を消す.
操作2 文字列S の末尾の文字を消す.
操作3 文字列S の先頭でも末尾でもない文字を消す.
操作3 を行うのは面倒なので,操作3 を行う回数をできるだけ少なくして,文字列S をレベルK のJOI
文字列に変換したい.
長さN の文字列S と1 以上の整数K が与えられたとき,文字列S をレベルK のJOI 文字列に変換する
のに必要な操作3 の回数の最小値を出力するプログラムを作成せよ.ただし,どのように操作を行っても
文字列S をレベルK のJOI 文字列に変換できない場合は,代わりに−1 を出力せよ.

• 3 ≦N ≦200 000.
• 1 ≦K ≦N
3 .
• S はJ, O, I の3 種類の文字からなる長さN の文字列である.

第19 回日本情報オリンピック(JOI 2019/2020) 本選
2020 年2 月9 日(茨城県つくば市)

1. (1 点) N ≦21.
2. (12 点) N ≦3 000.
3. (87 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.N, K は整数である.S は文字列である.
N K
S

文字列S をレベルK のJOI 文字列に変換するのに必要な操作3 の回数の最小値を1 行で出力せよ.ただ
し,どのように操作を行っても文字列S をレベルK のJOI 文字列に変換できない場合は,代わりに−1 を
出力せよ.

생성자가 기록되지 않았습니다.

출처 JOI 2020 Final