B - 回文分割

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は文字列 S を持っています。S は英小文字のみからなります。

まず、高橋君は S の文字を任意の順番に並べ替え、文字列 S' を作ります。

次に、高橋君は S' を任意の位置で分割し、何個かの文字列 s_1s_2...s_N を作ります(N は任意)。ただし、各 s_i は回文でなければなりません。

s_i の長さの最小値を X とします。高橋君は X をできるだけ大きくしようとしています。X の最大値を求めてください。

制約

  • 1≦|S|≦10^5
  • S は英小文字のみからなる。

入力

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

S

出力

X の最大値を出力せよ。


入力例1

rokovoko

出力例1

3

例えば、krkoovoo とすればよいです。


入力例2

tomtom

出力例2

6

例えば、mottom とすればよいです。


入力例3

vwxyz

出力例3

1

例えば、vwxyz とすればよいです。


入力例4

succeeded

出力例4

3