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 *k* contains this character *c*.

You have to find minimum *k* such that there exists at least one *k*-dominant character.
The first line contains string *s* consisting of lowercase Latin letters (1 ≤ |*s*| ≤ 100000).
none
abacaba
2
zzzzz
1
abcde
3
bcaccacaaabaacaabaaabcbbcbcaacacbcbaaaacccacbbcbaabcbacaacbabacacacaccbbccbcbacbbbbccccabcabaaab
8
daabcdabbabbacacbaacabacbcaabaacac
4
abghim
4
gfliflgfhhdkceacdljgkegmdlhcgkcmlelmbbbmdddgdeeljjhgbbffmemmmkhebgkhadkdajabcjkcgbkgbaeacdedlkklfech
17
a
1
aaabbb
4
ab
2
abbb
2
ob
2
abccba
3
saaaaaaaas
2
axxx
2
abcba
2
abb
2
abcdea
4
axcbb
3
tmivvdcbbfrfogjviirrximhttoskopwrcmkcborcxvr
13
dlchmmuateksgldkckljrovmeuniobjrelqjpnjljlvhpqrjsfklliqpufplgaelevmlcnodbllquubobecem
15
zx
2
zxz
2
bbhdgaefbhf
6
xx
1
zxx
2
cbcada
4
z
1
aab
2
jficc
3
cceeaabfba
5
jk
2
lzeznbwu
5
rr
1
#include <bits/stdc++.h>
#include <cxxabi.h>
#define eb emplace_back
#define X first
#define Y second
#define endl '\n'
#define tell(args...){string s_args=#args;replace(s_args.begin(),s_args.end(),',',' ');stringstream arg_names(s_args);istream_iterator<string>it(arg_names);cerr<<"["<<__LINE__<<"]  ";__tell(it,args);}
using namespace std;
template<class T>string get_type(T&&a){int stt;char*tmp=abi::__cxa_demangle(typeid(a).name(),0,0,&stt);string res(tmp);free(tmp);return res;}
template<class T>void __tell(auto&& name, T&& a){cerr<<"("<<get_type(a)<<")"<<name<<" = "<<a;}
template<class T>void __tell(istream_iterator<string>a_name,T&&a){__tell(*a_name, a);cerr<<"|\n";}
template<class T,class... Ts>void __tell(istream_iterator<string>a_name,T&&a,Ts&&...args){__tell(*a_name,a);cerr<<" --- ";__tell(++a_name,args...);}
typedef long long ll;
typedef pair<int, int> pii;
const int N = 100;
const int MOD = 1e9 + 7;
int main() {
    string s;
    cin >> s;
    vector<int> d[26];
    for (int i = 0; i < 26; ++i)
        d[i].push_back(0);
    for (int i = 0; i < s.length(); ++i)
        d[s[i] - 'a'].push_back(i);
    for (int i = 0; i < 26; ++i)
        d[i].push_back(s.length());
    int res = s.length();
    for (int i = 0; i < 26; ++i) {
        int t = 0;
        for (int j = 1; j < d[i].size(); ++j)
            t = max(t, d[i][j] - d[i][j - 1]);
        res = min(res, t);
    }
    cout << res;
}