AtCoder Grand Contest 016

A - Shrinking


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 300

問題文

すぬけ君は、次のルールに従い、長さ N の文字列 t を長さ N - 1 の文字列 t' へ変えることができます。

  • i (1 ≤ i ≤ N - 1) について、t'i 文字目は ti, i + 1 文字目のどちらかである。

英小文字のみからなる文字列 s があります。 すぬけ君の目標は、s に上記の操作を繰り返し行い、s が単一の文字のみからなるようにすることです。 目標を達成するために必要な操作回数の最小値を求めてください。

制約

  • 1 ≤ |s| ≤ 100
  • s は英小文字のみからなる。

入力

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

s

出力

目標を達成するために必要な操作回数の最小値を出力せよ。


入力例 1

serval

出力例 1

3

例えば、servalsrvvlsvvvvvv と変えればよいです。


入力例 2

jackal

出力例 2

2

例えば、jackalaacaaaaaa と変えればよいです。


入力例 3

zzz

出力例 3

0

最初から s が単一の文字のみからなっています。


入力例 4

whbrjpjyhsrywlqjxdbrbaomnw

出力例 4

8

8 回の操作によって、srrrrrrrrrrrrrrrrrr へ変えることができます。

Score : 300 points

Problem Statement

Snuke can change a string t of length N into a string t' of length N - 1 under the following rule:

  • For each i (1 ≤ i ≤ N - 1), the i-th character of t' must be either the i-th or (i + 1)-th character of t.

There is a string s consisting of lowercase English letters. Snuke's objective is to apply the above operation to s repeatedly so that all the characters in s are the same. Find the minimum necessary number of operations.

Constraints

  • 1 ≤ |s| ≤ 100
  • s consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s

Output

Print the minimum necessary number of operations to achieve the objective.


Sample Input 1

serval

Sample Output 1

3

One solution is: servalsrvvlsvvvvvv.


Sample Input 2

jackal

Sample Output 2

2

One solution is: jackalaacaaaaaa.


Sample Input 3

zzz

Sample Output 3

0

All the characters in s are the same from the beginning.


Sample Input 4

whbrjpjyhsrywlqjxdbrbaomnw

Sample Output 4

8

In 8 operations, he can change s to rrrrrrrrrrrrrrrrrr.


Submit提出する