题目描述

对于给定的由小写字母组成的字符串 $\red{s，}$

当且仅当对于每个长度不小于$\red{k }$的 $\red{s}$的子串都含有字符 $\red{c，}$

那么我们称 $\red{c}$为 $\red{s}$的 $\red{k}$-主导字符。

请找出一个需要给出一个最小的$\red{k}$ ，使得对于给定的 $\red{s}$至少存在一个 $\red{k}$-主导字符。

本题输入量较大，请使用较快的输入方式。

输入格式

一个由小写字母组成的字符串$\red{s }$。

输出格式

一个整数，表示答案。

样例

输入样例1

abacaba

输出样例1

2

输入样例2

zzzzz

输出样例2

1

提示

对于$\red{30\%}$的数据，有$\red{1≤}$$\red{|s|≤}$$\red{300}$;

对于$\red{60\%}$的数据，有$\red{1≤}$$\red{|s|≤}$$\red{5000}$;

对于$\red{80\%}$的数据，有$\red{1≤}$$\red{|s|≤}$$\red{100000}$;

对于$\red{100\%}$的数据，有$\red{1≤}$$\red{|s|≤}$$\red{11000000}$。