実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 300 点
問題文
すぬけ君は、次のルールに従い、長さ N の文字列 t を長さ N - 1 の文字列 t' へ変えることができます。
- 各 i (1 ≤ i ≤ N - 1) について、t' の i 文字目は t の i, i + 1 文字目のどちらかである。
英小文字のみからなる文字列 s があります。 すぬけ君の目標は、s に上記の操作を繰り返し行い、s が単一の文字のみからなるようにすることです。 目標を達成するために必要な操作回数の最小値を求めてください。
制約
- 1 ≤ |s| ≤ 100
- s は英小文字のみからなる。
入力
入力は以下の形式で標準入力から与えられる。
s
出力
目標を達成するために必要な操作回数の最小値を出力せよ。
入力例 1
serval
出力例 1
3
例えば、serval
→ srvvl
→ svvv
→ vvv
と変えればよいです。
入力例 2
jackal
出力例 2
2
例えば、jackal
→ aacaa
→ aaaa
と変えればよいです。
入力例 3
zzz
出力例 3
0
最初から s が単一の文字のみからなっています。
入力例 4
whbrjpjyhsrywlqjxdbrbaomnw
出力例 4
8
8 回の操作によって、s を rrrrrrrrrrrrrrrrrr
へ変えることができます。
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: serval
→ srvvl
→ svvv
→ vvv
.
Sample Input 2
jackal
Sample Output 2
2
One solution is: jackal
→ aacaa
→ aaaa
.
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
.