D - ヘイホー君と削除 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ある文字列を 2 回繰り返してできる文字列を、平方と呼びます。 たとえば、abcabcabababab は平方ですが、 abcababab は平方ではありません。 なお、長さ 0 の文字列も、平方とみなすことにします。

ヘイホー君はある日、英小文字のみからなる文字列 S を、道端で拾いました。 平方が好きなヘイホー君は、 文字列 S に以下の操作を繰り返すことで、平方を得ようと考えました。

  • 1 ≦ p ≦ |S| を満たす整数 p を選ぶ。その後、Sp 文字目を削除する。ここで、|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 という平方を得ることができます。