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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int INF = 0x3f3f3f3f;

const int MAXS = 26;

void solve() {
    string s; cin >> s;

    int n = s.length();
    s = " " + s;

    // pre[ch]表示字符ch出现次数的前缀和
    vector<vector<int>> pre(n + 1, vector<int>(MAXS));
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1];
        pre[i][s[i] - 'a']++;
    }

    auto check = [&](int k)->bool {
        vector<int> cnt(MAXS, INF);  // 所有长度为k的子串中每个字符出现次数的最小值
        for (int r = k; r <= n; r++) {
            int l = r - k + 1;
            for (int i = 0; i < MAXS; i++)
                cnt[i] = min(cnt[i], pre[r][i] - pre[l - 1][i]);
        }
        
        for (int i = 0; i < MAXS; i++) 
            if (cnt[i]) return true;
        return false;
    };

    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    // init();
    // CaseT
    solve();
    return 0;
}
	 		 		  	 	 			  	 	  		   		