B - ヘイホー君と置き換え Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ある文字列を 2 回繰り返してできる文字列を、平方と呼びます。 たとえば、abcabc や abababab は平方ですが、 abc や ababab は平方ではありません。

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

  • 1 ≦ p ≦ N を満たす整数 p と、英小文字 c を選ぶ。その後、S の p 文字目を c に置き換える。

ヘイホー君が平方を得るために必要な操作回数の最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N
S
  • 1 行目には、整数 N (1 ≦ N ≦ 100) が与えられる。これはヘイホー君が拾った文字列の長さを表す。
  • 2 行目には、ヘイホー君が拾った文字列 S が与えられる。S は英小文字のみからなる N 文字の文字列であることが保証される。

出力

もしヘイホー君が平方を得ることができないならば、-1 を 1 行に出力せよ。 平方を得ることができるならば、そのために必要な最小の操作回数を 1 行に出力せよ。 いずれの場合も、出力の末尾には改行をいれること。

入力例1

8
abacbabc

出力例1

3

以下のように 3 回の操作を行うことで、aabcaabc という平方を得ることができます。

  • 2 文字目を a に置き換え、aaacbabc にする。
  • 3 文字目を b に置き換え、aabcbabc にする。
  • 5 文字目を a に置き換え、aabcaabc にする。

入力例2

8
abababab

出力例2

0

abababab は平方なので、一度も操作を行う必要はありません。

入力例3

5
abcde

出力例3

-1

どのように操作を行っても平方を得ることはできません。

入力例4

26
codefestivaltwozeroonefive

出力例4

11