C. K-Dominant Character

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a string s consisting of lowercase Latin letters. Character c is called k-dominant iff each substring of s with length at least kcontains this character c.

You have to find minimum k such that there exists at least one k-dominant character.

Input

The first line contains string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 100000).

Output

Print one number — the minimum value of k such that there exists at least one k-dominant character.

Examples

input

abacaba

output

2

input

zzzzz

output

1

input

abcde

output

3

题意：

让你找一个最小的长度k，使得所有子串中存在一个相同的字符c

代码： #include 
       
         #include 
        
          #include 
         
           /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; bool f[100005]; int main() {
      string s;  char c;  int len;  cin>>s;  len=s.length();  int mine=len/2+1,maxn,k=0;  for(int i=0;i