D - ヘイホー君と削除
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ある文字列を 2 回繰り返してできる文字列を、平方と呼びます。
たとえば、abcabc
や abababab
は平方ですが、
abc
や ababab
は平方ではありません。
なお、長さ 0 の文字列も、平方とみなすことにします。
ヘイホー君はある日、英小文字のみからなる文字列 S を、道端で拾いました。 平方が好きなヘイホー君は、 文字列 S に以下の操作を繰り返すことで、平方を得ようと考えました。
- 1 ≦ p ≦ |S| を満たす整数 p を選ぶ。その後、S の p 文字目を削除する。ここで、|S| は S の長さを表すものとする。
ヘイホー君が平方を得るために必要な操作回数の最小値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N S
- 1 行目には、整数 N (1 ≦ N ≦ 100) が与えられる。これはヘイホー君が拾った文字列の長さを表す。
- 2 行目には、ヘイホー君が拾った文字列 S が与えられる。S は英小文字のみからなる N 文字の文字列であることが保証される。
出力
ヘイホー君が平方を得るために必要な最小の操作回数を 1 行に出力せよ。 出力の末尾には改行をいれること。
入力例1
8 abacbabc
出力例1
2
以下のように 2 回の操作を行うことで、abcabc
という平方を得ることができます。
- 5 文字目を削除し、
abacabc
にする。 - 3 文字目を削除し、
abcabc
にする。
入力例2
8 abababab
出力例2
0
abababab
は平方なので、一度も操作を行う必要はありません。
入力例3
5 abcde
出力例3
5
すべての文字を削除することで、長さ 0 の平方を得ることができます。
入力例4
26 codefestivaltwozeroonefive
出力例4
14
oefiveoefive
という平方を得ることができます。