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
import collections
import queue
from sys import stdin, stdout

input_int = lambda: int(stdin.readline())
input_1D_int = lambda: [int(x) for x in stdin.readline().split()]
input_2D_int = lambda n: [input_1D_int() for _ in range(n)]
input_string = lambda: stdin.readline().strip()
input_1D_string = lambda: [str(x) for x in stdin.readline().split()]
input_2D_string = lambda n: [input_1D_string() for _ in range(n)]
pr = lambda args, sep: stdout.write(sep.join(map(str, args)) + '\n')
chars, oo = 'abcdefghijklmnopqrstuvwxyz', int(1e18)
a = input_string()
prefix = []
for i in range(26):
    b = [0] * (len(a) + 1)
    for j in range(len(a)):
        b[j + 1] = (a[j] == chars[i]) + b[j]
    prefix.append(b)
l, r, best = 0, len(a), len(a)

def can (k):
    for i in range(26):
        f = 1
        for j in range(len(a) - k):
             f &= (prefix[i][j + k] - prefix[i][j]) != 0
        if f == 1:
             return 1
    return 0
while l <= r:
    mid = (l + r) // 2
    if can(mid):
        best = mid
        r = mid - 1
    else:
        l = mid + 1
print(best)
