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.


-----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

Difficulty: MEDIUM
Tags: Sorting

Amortized analysis

Implementation
Skill types: Sorting

Amortized analysis

Starter code:

Solutions:
s = input()
d = dict()
for i in range(len(s)):
	el = s[i]
	try:
		d[el].append(i)
	except KeyError:
		d[el] = [-1, i]
for i in d.keys():
	d[i].append(len(s))
a = list()
for i in d.keys():
	t = [d[i][j] - d[i][j - 1] for j in range(1, len(d[i]))]
	a.append(max(t))
print(min(min(a), (len(s) + 2) // 2))


import sys
s = [ord(c) - 97 for c in input()]
n = len(s)

def solve(k):
	(count, res) = ([0] * 26, [1] * 26)
	for i in range(k):
		count[s[i]] += 1
	for cc in range(26):
		if count[cc] == 0:
			res[cc] = 0
	for i in range(k, n):
		count[s[i]] += 1
		count[s[i - k]] -= 1
		for cc in range(26):
			if count[cc] == 0:
				res[cc] = 0
	return max(res) > 0
(ok, ng) = (n, 0)
while abs(ok - ng) > 1:
	mid = ok + ng >> 1
	if solve(mid):
		ok = mid
	else:
		ng = mid
print(ok)


s = input()
alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
occ = {}
for ltr in alphabet:
	occ[ltr] = [0, len(s) + 1]
for i in range(len(s)):
	occ[s[i]].append(i + 1)
k = 10 ** 9
for ltr in alphabet:
	kspec = 0
	occ[ltr].sort()
	for i in range(1, len(occ[ltr])):
		kspec = max(kspec, occ[ltr][i] - occ[ltr][i - 1])
	k = min(k, kspec)
print(k)


import sys
import math
import operator as op
from functools import reduce
from sys import maxsize

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom

def nc2(n):
	return n * (n - 1) // 2
t = 1
for i in range(t):
	s = read_line()
	d = {}
	for i in range(len(s)):
		if s[i] in d:
			d[s[i]].append(i)
		else:
			d[s[i]] = [i]
	for i in d:
		d[i] = [-1] + d[i]
		d[i].append(len(s))
	ans = 1000000000.0
	for i in d:
		v = -1
		for j in range(len(d[i]) - 1):
			v = max(d[i][j + 1] - d[i][j], v)
		if v == -1:
			break
		ans = min(v, ans)
	print(ans)


s = input()
l = len(s)
d = [[-1, 0, -1] for i in range(26)]
k = [-1 for i in range(26)]
for i in range(l):
	n = ord(s[i]) - 97
	if d[n][0] == -1:
		d[n][0] = i
		d[n][2] = i
	else:
		d[n][1] = max(d[n][1], i - d[n][0])
		d[n][0] = i
ans = l
for i in range(26):
	if d[i][0] != -1:
		k[i] = max(d[i][2], l - d[i][0] - 1, d[i][1] - 1)
	if k[i] > -1:
		ans = min(ans, k[i])
print(ans + 1)


from collections import defaultdict
s = input()
symbols = defaultdict(list)
for (i, c) in enumerate(s):
	symbols[c].append(i)
dists = defaultdict(list)
for (c, coords) in symbols.items():
	deltas = []
	deltas.append(coords[0] + 1)
	for x in range(1, len(coords)):
		deltas.append(coords[x] - coords[x - 1])
	deltas.append(len(s) - coords[-1])
	dists[c] = deltas
ans = (len(s) + 2) // 2
for c in dists.keys():
	if len(dists[c]) > 0:
		ans = min(ans, max(dists[c]))
print(ans)


import sys
st = sys.stdin.readline()
le = len(st) - 1
cind = []
cdif = []
for i in range(26):
	cind.append(-1)
	cdif.append(-1)
for i in range(le):
	c = ord(st[i]) - ord('a')
	cdif[c] = max(i - cind[c], cdif[c])
	cind[c] = i
for i in range(26):
	cdif[i] = max(le - cind[i], cdif[i])
mi = le
for i in range(26):
	if cdif[i] != -1:
		mi = min(cdif[i], mi)
print(mi)


s = input()
mn = 1000000000.0
le = len(s)
for i in range(26):
	c = chr(97 + i)
	pos = s.find(c)
	cur = pos + 1
	if pos == -1:
		continue
	while True:
		pos2 = s.find(c, pos + 1)
		if pos2 == -1:
			cur = max(cur, le - pos)
			break
		cur = max(cur, pos2 - pos)
		pos = pos2
	mn = min(cur, mn)
print(mn)


s = input()
letters = set(s)
ans = len(s)
for ch in letters:
	prev = -1
	max_dist = 0
	for pos in range(len(s)):
		if s[pos] == ch:
			max_dist = max(pos - prev - 1, max_dist)
			prev = pos
	max_dist = max(len(s) - prev - 1, max_dist)
	ans = min(ans, max_dist + 1)
print(ans)


from collections import defaultdict
s = input()
d = {}
d = defaultdict(lambda : [0], d)
d1 = {}
d1 = defaultdict(lambda : -1, d1)
k = 1
for i in s:
	d1[i] = max(k - d[i][-1], d1[i])
	d[i].append(k)
	k += 1
ans = []
for i in d.keys():
	d1[i] = max(len(s) - d[i][-1] + 1, d1[i])
for i in d1.keys():
	if len(d[i]) > 2:
		ans.append(d1[i])
if len(ans) == 0:
	print(len(s) // 2 + 1)
else:
	print(min(min(ans), len(s) // 2 + 1))


S = [ord(c) - ord('a') for c in input()]
K = [float('inf')] * 26
L = [None] * 26
for i in range(len(S)):
	if L[S[i]] == None:
		K[S[i]] = i + 1
	elif i - L[S[i]] > K[S[i]]:
		K[S[i]] = i - L[S[i]]
	L[S[i]] = i
for i in range(26):
	if L[i] != None and len(S) - L[i] > K[i]:
		K[i] = len(S) - L[i]
print(min(K))


inp = input()
places = {}
for (ind, l) in enumerate(inp):
	if l not in places:
		places[l] = [-1]
	places[l].append(ind)
for l in places:
	places[l].append(len(inp))
print(min((max([j - i for (i, j) in zip(places[l][:-1], places[l][1:])]) for l in places)))


import string
s = input()
ans = len(s) // 2 + 1
for a in list(string.ascii_lowercase):
	last = -1
	l = 0
	for (i, c) in enumerate(list(s)):
		if a == c:
			l = max(l, i - last)
			last = i
	l = max(l, len(s) - last)
	ans = min(ans, l)
print(ans)


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def lcm(x, y):
	return x * y / gcd(x, y)

def fact(x, mod=mod):
	ans = 1
	for i in range(1, x + 1):
		ans = ans * i % mod
	return ans

def arr2D(n, m, default=0):
	lst = []
	for i in range(n):
		temp = [default] * m
		lst.append(temp)
	return lst

def sortDictV(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}
s = float('inf')
a = input()
for i in set(a):
	leng = 0
	for j in a.split(i):
		leng = max(leng, len(j))
	s = min(leng, s)
print(s + 1)


C = 'qwertyuiopasdfghjklzxcvbnm'
s = input()
l = len(s)
mini = l + 1
for c in C:
	last = -1
	max_l = 0
	for i in range(l):
		if s[i] == c:
			max_l = max(max_l, i - last)
			last = i
	max_l = max(max_l, l - last)
	mini = min(mini, max_l)
print(mini)


s = input()
m = 1000000000
for l in set(s):
	x = set(s.split(l))
	m = min(m, len(max(x, key=len)))
print(m + 1)


from collections import defaultdict

def main(s):
	d = {}
	n = len(s)
	for (i, c) in enumerate(s):
		if c in d:
			delta = i - d[c][1] - 1
			if delta > d[c][0]:
				d[c] = (delta, i)
			else:
				d[c] = (d[c][0], i)
		else:
			delta = i
			d[c] = (delta, i)
	for (c, (gap, idx)) in d.items():
		if gap < n - 1 - idx:
			d[c] = (n - 1 - idx, n)
	return min((c for (c, _) in d.values())) + 1
s = input()
print(main(s))


from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
a = input().strip()
n = len(a)
mp = defaultdict(list)
for i in range(n):
	mp[a[i]].append(i)
for i in a:
	mp[i].append(n)
res = n // 2 + 1
for c in mp.keys():
	mx = max(mp[c][0] + 1, 0)
	tmp = mp[c]
	for (i, v) in enumerate(tmp):
		mx = max(mx, v - tmp[i - 1])
	res = min(res, mx)
print(res)


import math
s = input()
ans = math.inf
for i in set(s):
	ans = min(ans, max(map(len, s.split(i))) + 1)
print(ans)


s = input()
min_ = 10 ** 6
for i in list(set(s)):
	if max(map(len, s.split(i))) < min_:
		min_ = max(map(len, s.split(i)))
print(min_ + 1)


s = input()
mx = []
for i in set(s):
	mx.append(max(map(len, s.split(i))))
print(min(mx) + 1)


def parse(s):
	l = []
	for i in range(len(s)):
		if s[i] not in l:
			l.append(s[i])
	return l

def main(s):
	l = parse(s)
	counttemp = 1
	count = []
	lc = []
	for i in range(len(l)):
		for j in range(len(s)):
			if l[i] == s[j]:
				count.append(counttemp)
				counttemp = 1
			else:
				counttemp = counttemp + 1
		count.append(counttemp)
		lc.append(max(count))
		count = []
		counttemp = 1
	return min(lc)
print(main(input()))


s = input()
c = []
f = 0
for i in s:
	if i not in c:
		c.append(i)
j = []
for i in c:
	n = 0
	m = 0
	for i2 in i + s + i:
		if i2 == i:
			n += 1
			if n > m:
				m = n
			n = 0
		else:
			n += 1
	j.append(m)
print(min(j))


from math import ceil
s = input()

def isgood(k):
	d = {}
	q = set(s[:k])
	for x in range(26):
		d[chr(x + ord('a'))] = 0
	for x in range(k):
		d[s[x]] += 1
	for x in range(k, len(s)):
		d[s[x - k]] -= 1
		d[s[x]] += 1
		tmp = q.copy()
		for y in q:
			if d[y] == 0:
				tmp.remove(y)
		q = tmp
		if len(q) == 0:
			break
	return len(q) > 0
l = 0
r = len(s)
while r - l > 1:
	mid = ceil((r + l) / 2)
	if isgood(mid):
		r = mid
	else:
		l = mid
print(r)


def good(k, s):
	for i in range(26):
		c = chr(ord('a') + i)
		count = 0
		ok = True
		for j in range(len(s)):
			if s[j] == c:
				count += 1
			if j >= k and s[j - k] == c:
				count -= 1
			if count == 0 and j + 1 >= k:
				ok = False
				break
		if ok:
			return True
	return False

def k_dominant_character(s):
	low = 0
	high = len(s)
	while low + 1 < high:
		mid = (high + low) // 2
		if good(mid, s):
			high = mid
		else:
			low = mid
	return high
s = input()
print(k_dominant_character(s))


s = input()
l = len(s)
ans = 10000000000
arr = [[0, -1] for i in range(26)]
for i in range(l):
	k = ord(s[i]) - ord('a')
	arr[k][0] = max(i - arr[k][1], arr[k][0])
	arr[k][1] = i
for i in range(26):
	arr[i][1] = -1
for i in range(l - 1, -1, -1):
	k = ord(s[i]) - ord('a')
	if arr[k][1] == -1:
		arr[k][0] = max(l - i, arr[k][0])
		arr[k][1] = i
for i in range(26):
	if arr[i][1] != -1:
		ans = min(ans, arr[i][0])
print(ans)


s = input()
d = {}
n = len(s)
for i in range(n):
	t = s[i]
	try:
		d[t].append(i + 1)
	except KeyError:
		d[t] = [0, i + 1]
ma = 99999999
for i in d:
	l = d[i]
	l.append(n + 1)
	to = 0
	for j in range(1, len(l)):
		to = max(to, l[j] - l[j - 1])
	ma = min(ma, to)
print(ma)


seq = input()
n = len(seq)
s = set(seq)
dic = dict()
for i in s:
	dic[i] = [0, 0]
for i in range(n):
	c = seq[i]
	if i + 1 - dic[c][0] > dic[c][1]:
		dic[c][1] = i + 1 - dic[c][0]
	dic[c][0] = i + 1
mi = 100000
for i in s:
	if n - dic[i][0] + 1 > dic[i][1]:
		dic[i][1] = n - dic[i][0] + 1
	if dic[i][1] < mi:
		mi = dic[i][1]
print(mi)


st = input()
ans = len(st)
for ch in set(list(st)):
	last = 0
	maxdif = 0
	for i in range(len(st)):
		if ch == st[i]:
			maxdif = max(maxdif, i - last)
			last = i + 1
	ans = min(ans, max(maxdif, len(st) - last))
print(ans + 1)


s = input()
l = []
for i in s:
	if i not in l:
		l.append(i)
minans = len(s) // 2 + 1
bst = -1
bfn = -1
for i in l:
	j = -1
	ans = 0
	st = s.find(i, 0)
	fn = len(s) - s[::-1].find(i, 0) - 1
	while s.find(i, j + 1) != -1:
		k = j
		j = s.find(i, j + 1)
		raz = j - k
		ans = max(ans, raz)
		ans = max(ans, max(st + 1, len(s) - fn))
	if ans < minans:
		minans = ans
print(minans)


s = input()
letras = set(s)
resp = len(s)
for x in letras:
	ant = -1
	max_dist = 0
	for atual in range(len(s)):
		if s[atual] == x:
			max_dist = max(atual - ant, max_dist)
			ant = atual
	max_dist = max(len(s) - ant, max_dist)
	resp = min(resp, max_dist)
print(resp)


import math
import collections
l = list(input())
n = len(l)
l1 = [0] * n
d = {}
for i in range(n):
	if l[i] not in d:
		if i == 0:
			d[l[i]] = [i]
		else:
			d[l[i]] = [-1, i]
	else:
		d[l[i]].append(i)
for i in d:
	if d[i][-1] != n - 1:
		d[i].append(n)
m = n
d = collections.OrderedDict(sorted(d.items()))
for i in d:
	d1 = 0
	for j in range(len(d[i]) - 1):
		d1 = max(d1, d[i][j + 1] - d[i][j])
	for j in range(d1 - 1, m):
		l1[j] = i
	m = min(m, d1 - 1)
print(max(1, m + 1))


s = input()

def dominant(string, k):
	if not k in string:
		return len(string) + 1
	else:
		last_pointer = -1
		kmap = []
		for (i, x) in enumerate(string):
			if x == k:
				gap = i - last_pointer - 1
				last_pointer = i
				kmap.append(gap)
			else:
				pass
		gap = len(string) - last_pointer - 1
		kmap.append(gap)
		return max(kmap) + 1
ans_candidates = []
for x in 'abcdefghijklmnopqrstuvwxyz':
	ans_candidates.append(dominant(s, x))
print(min(ans_candidates))


s = list(input())
n = len(s)
idx = [[-1] for _ in range(26)]
for i in range(n):
	idx[ord(s[i]) - ord('a')].append(i)
for i in range(26):
	idx[i].append(n)
print(min(map(lambda ls: max(map(lambda i: ls[i + 1] - ls[i], range(len(ls) - 1))), idx)))


s = input()
a = set()
for char in s:
	a.add(char)
ans = list()
for i in a:
	n = list()
	n.append(-1)
	n.append(s.__len__())
	for j in range(0, s.__len__()):
		if i == s[j]:
			n.append(j)
	r = list()
	n = sorted(n)
	for j in range(1, n.__len__()):
		r.append(abs(n[j] - n[j - 1]))
	ans.append(sorted(r)[-1])
print(sorted(ans)[0])


s = input()
chars = list(set(s))
print(min((max(map(len, s.split(c))) + 1 for c in chars)))


l = [ord(i) - 97 for i in input()]
maxi = {}
n = len(l)
seen = {}
for i in range(26):
	seen[i] = -1
for i in range(26):
	maxi[i] = -2347238
for i in range(n):
	maxi[l[i]] = max(maxi[l[i]], i - seen[l[i]])
	seen[l[i]] = i
for i in range(n):
	maxi[l[i]] = max(maxi[l[i]], n - seen[l[i]])
minim = 10000000000000
for i in range(26):
	if i not in l:
		continue
	if maxi[i] < minim:
		minim = maxi[i]
		ans = i
print(minim)


import sys
from collections import Counter

def max_d(string, alpha, occur):
	if occur == 1:
		return len(string) // 2 + 1
	prev = -1
	max_d = 0
	for (index, i) in enumerate(s):
		if i == alpha:
			if index - prev > max_d:
				max_d = index - prev
			prev = index
	return max(max_d, len(s) - prev)
s = sys.stdin.readline().rstrip()
c = Counter(s)
print(min((max_d(s, k, v) for (k, v) in c.items())))


def check(s, m):
	for c in range(ord('a'), ord('z') + 1):
		cnt = 0
		for i in range(0, m):
			if s[i] == chr(c):
				cnt += 1
		if cnt == 0:
			continue
		flag = True
		for i in range(m, len(s)):
			if s[i - m] == chr(c):
				cnt -= 1
			if s[i] == chr(c):
				cnt += 1
			if cnt == 0:
				flag = False
				break
		if flag == True:
			return True
	return False
s = input()
l = 0
r = len(s)
while l + 1 < r:
	m = l + (r - l >> 1)
	if check(s, m) == True:
		r = m
	else:
		l = m
print(r)


from string import ascii_lowercase as lower
string = input()
d = {char: [-1] for char in lower}
for i in range(len(string)):
	d[string[i]].append(i)
ans = 100000
for char in lower:
	d[char].append(len(string))
	if len(d[char]) > 2:
		m = 0
		for i in range(len(d[char]) - 1):
			m = max(m, d[char][i + 1] - d[char][i])
		ans = min(ans, m)
print(ans)


s = str(input())
tot = len(s)
count = [-1] * 26
temp = [0] * 26
for i in range(0, tot):
	for j in range(0, 26):
		if j != ord(s[i]) - ord('a'):
			temp[j] += 1
		elif j == ord(s[i]) - ord('a'):
			temp[j] += 1
			count[j] = max(count[j], temp[j])
			temp[j] = 0
for j in range(0, 26):
	if count[j] != 0:
		count[j] = max(count[j], temp[j] + 1)
print(min(count))


s = input()
a = 96
b = 0
d = 100000000000
for i in range(26):
	a = a + 1
	c = b = 0
	for j in range(len(s)):
		if s[j] == chr(a):
			c = 0
		else:
			c = c + 1
			if b < c:
				b = c
	if b < d:
		d = b
print(d + 1)


s = ' ' + input()
dom = {}
lastpos = {}
for i in ' abcdefghijklmnopqrstuvwxyz':
	dom[i] = 10000000000000
	lastpos[i] = 0
for (i, si) in enumerate(s):
	if dom[si] > 1000000:
		dom[si] = 0
	dom[si] = max(dom[si], i - lastpos[si])
	lastpos[si] = i
for i in ' abcdefghijklmnopqrstuvwxyz':
	dom[i] = max(dom[i], len(s) - lastpos[i])
dom.pop(' ')
print(min(dom.values()))


hash = {}
s = input()
for i in range(len(s)):
	if s[i] in hash:
		if i - hash[s[i]][0] > hash[s[i]][1]:
			hash[s[i]][1] = i - hash[s[i]][0]
		hash[s[i]][0] = i
	else:
		hash[s[i]] = [i, i + 1]
chars = set([i for i in s])
for i in hash.keys():
	if len(s) - hash[i][0] > hash[i][1]:
		hash[i][1] = len(s) - hash[i][0]
	hash[i][0] = len(s) - 1
mini = len(s)
for i in hash.keys():
	if hash[i][1] < mini:
		mini = hash[i][1]
print(mini)


s = input()
ans = len(s)
import string
for l in string.ascii_lowercase:
	d = 0
	cd = 0
	pv = True
	for i in range(len(s)):
		if s[i] == l:
			if pv:
				cd += 1
				pv = False
			d = max(d, cd)
			cd = 1
		else:
			cd += 1
	cd = max(d, cd)
	ans = min(cd, ans)
print(ans)


word = input()
ans = []
for c in set(list(word)):
	maior_dist = 0
	atual_dist = 0
	last_pos = 0
	for (i, let) in enumerate(word):
		if let == c:
			atual_dist += 1
			if atual_dist > maior_dist:
				maior_dist = atual_dist
			atual_dist = 0
			last_pos = i
		else:
			atual_dist += 1
	if atual_dist > maior_dist:
		maior_dist = atual_dist
	ans.append(max(maior_dist, len(word) - last_pos))
print(min(ans))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
s = input()
mn = len(s)
for i in range(97, 123):
	c = 0
	mx = 0
	for j in range(len(s)):
		if s[j] == chr(i):
			mx = max(mx, c)
			c = 0
		else:
			c += 1
	mx = max(mx, c)
	mn = min(mn, mx)
print(mn + 1)


s = input()
n = len(s)
k = 1
sim = set(s[0])
a = [0] * n
a[0] = 1
sim = set(s)
d = dict()
for i in sim:
	d[i] = [-1, 1]
for i in range(n):
	d[s[i]][1] = max(d[s[i]][1], i - d[s[i]][0])
	d[s[i]][0] = i
k = 10000000
for i in d.values():
	k = min(k, max(n - i[0], i[1]))
print(k)


import sys
import math

def check(L):
	vis = [True for i in range(26)]
	cnt = [0 for i in range(26)]
	for i in range(L):
		val = s[i]
		cnt[val] += 1
	for i in range(len(cnt)):
		if not cnt[i]:
			vis[i] = False
	for i in range(L, len(s)):
		val = s[i]
		cnt[val] += 1
		val = s[i - L]
		cnt[val] -= 1
		if not cnt[val]:
			vis[val] = False
	for i in vis:
		if i:
			return True
	return False
s = list(map(lambda x: ord(x) - ord('a'), input()))
l = 0
r = len(s)
while r > l:
	mid = l + r >> 1
	if check(mid):
		r = mid
	else:
		l = mid + 1
print(l)


import string
from collections import defaultdict
s = input()
window = defaultdict(list)
character_set = string.ascii_lowercase
(n, ans) = (len(s), len(s))
for (idx, char) in enumerate(character_set):
	prev = -1
	consider = -10 ** 9 - 7
	for (jdx, x) in enumerate(s):
		if x == char:
			consider = max(consider, jdx - prev)
			prev = jdx
	consider = max(consider, n - prev)
	if prev != -1:
		ans = min(ans, consider)
print(ans)


from __future__ import division, print_function
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	a = list(inp())
	n = len(a)
	ans = n
	for i in range(97, 97 + 26):
		curr = chr(i)
		prev = -1
		k = -1
		for j in range(n):
			if j == n - 1:
				k = max(k, j - prev if a[j] == curr else j - prev + 1)
			elif a[j] == curr:
				k = max(k, j - prev)
				prev = j
		ans = min(ans, k)
	print(ans)
testcase(1)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
s = input()
st = [-1 for i in range(26)]
gap = [0 for i in range(26)]
n = len(s)
for i in range(n):
	r = i - st[ord(s[i]) - 97]
	gap[ord(s[i]) - 97] = max(gap[ord(s[i]) - 97], r)
	st[ord(s[i]) - 97] = i
ans = n
t = 0
for i in gap:
	i = max(i, n - st[t])
	if i != 0:
		ans = min(ans, i)
	t += 1
print(ans)


i = input()
s = set(i)

def F(c):
	l = [i + 1 for (i, x) in enumerate(i) if x == c]
	d = (y - x for (x, y) in zip(l, l[1:]))
	return max(l[0], len(i) - l[-1] + 1, *d)
print(min(map(F, s)))


def main():
	s = input()
	(lo, hi) = (0, len(s))
	while lo + 1 < hi:
		mid = (lo + hi) // 2
		cnt = dict.fromkeys('abcdefghijklmnopqrstuvwxyz', 0)
		for i in range(mid):
			cnt[s[i]] += 1
		v = {c for (c, x) in cnt.items() if not x}
		for (i, c) in zip(range(mid, len(s)), s):
			cnt[s[i]] += 1
			cnt[c] -= 1
			if not cnt[c]:
				v.add(c)
		if len(v) < 26:
			hi = mid
		else:
			lo = mid
	print(hi)
main()


s = input()
c = list(set(s))
ans = 1000000000
for x in c:
	y = max(map(len, s.split(x)))
	if y < ans:
		ans = y
print(ans + 1)


s = input()
B = []
k = len(s) // 2 + 1
A = 'abcdefghijklmnopqrstuvwxyz'
minmax = len(s)
for q in range(len(s)):
	B.append(s[q])
for q in range(len(A)):
	d = 0
	C = B.copy()
	C = [A[q]] + C
	C.append(A[q])
	max = 0
	for e in range(len(s) + 2):
		if C[e] == A[q]:
			if e - d > max:
				max = e - d
			d = e
	if max < minmax:
		minmax = max
print(minmax)


s = float('inf')
a = input()
for i in list(set(a)):
	leng = max(list(map(len, a.split(i))))
	if leng < s:
		s = leng
print(s + 1)


a = [chr(i) for i in range(ord('a'), ord('z') + 1)]
s = input()
min_dom = len(s)
for letter in a:
	if letter in s:
		cur = s.index(letter) + 1
		last = cur - 1
		ll = cur - 1
		for j in range(ll + 1, len(s)):
			if s[j] == letter:
				cur = max(cur, j - last)
				last = j
		min_dom = min(min_dom, max(cur, len(s) - last))
print(min_dom)


def every_seg(A, k, c):
	amount = 0
	for i in range(k - 1):
		if A[i] == c:
			amount += 1
	for i in range(k - 1, len(A)):
		if A[i] == c:
			amount += 1
		if amount == 0:
			return False
		if A[i - k + 1] == c:
			amount -= 1
	return True
S = input()
all_letters = [chr(ord('a') + i) for i in range(26)]
(a, b, c) = (1, len(S), 0)
while a < b:
	c = (a + b) // 2
	if any([every_seg(S, c, letter) for letter in all_letters]):
		b = c
	else:
		a = c + 1
print(a)


s = input()
cs = {}
ma = {}
keys = 'abcdefghijklmnopqrstuvwxyz'
for c in keys:
	cs[c] = []
	ma[c] = -1
for i in range(len(s)):
	c = s[i]
	cs[c].append(i)
for c in keys:
	if len(cs[c]) > 0:
		ma[c] = max(cs[c][0] + 1, len(s) - cs[c][-1])
	for i in range(1, len(cs[c])):
		if abs(cs[c][i] - cs[c][i - 1]) > ma[c]:
			ma[c] = abs(cs[c][i] - cs[c][i - 1])
mi = 9999999999
for m in ma.values():
	if m != -1 and m < mi:
		mi = m
print(mi)


from collections import defaultdict
mi = defaultdict(lambda : 100001)
ma = defaultdict(lambda : -1)
mgap = defaultdict(int)
ind = defaultdict(lambda : -1)
s = input()
n = len(s)
for i in range(n):
	if ind[s[i]] == -1:
		mi[s[i]] = i
		ma[s[i]] = i
		ind[s[i]] = i
	else:
		ma[s[i]] = i
		mgap[s[i]] = max(mgap[s[i]], i - ind[s[i]] - 1)
		ind[s[i]] = i
sa = set(ind.keys())
mini = 100001
for i in sa:
	mini = min(mini, max(max(n - 1 - ma[i], mi[i]), mgap[i]))
print(mini + 1)


s = str(input())
s = list(s)
n = len(s)
S = set(s)
S = list(S)
N = len(S)
l = [[] for i in range(N)]
r = [-1 for i in range(N)]
for i in range(n):
	for j in range(N):
		if s[i] == S[j]:
			l[j].append(i)
			break
for i in range(N):
	l[i] = [-1] + l[i] + [n]
for i in range(N):
	for j in range(1, len(l[i])):
		r[i] = max(r[i], l[i][j] - l[i][j - 1])
print(min(r))


def main():
	s = input()
	checked = []
	l = len(s)
	mi = l // 2 + 1
	for i in range(l):
		if s[i] not in checked:
			j = i + 1
			m = i + 1
			t = i
			while j < l:
				while j < l and s[t] != s[j]:
					j += 1
				if j - t > m:
					m = j - t
				t = j
				j += 1
			if m < mi:
				mi = m
			checked += [s[i]]
	print(mi)
main()


from collections import defaultdict
import math
from sys import stdin
index = 0
string = stdin.readline().strip()
L = len(string)
letterList = []
position = defaultdict(list)
output = L
for letter in string:
	letterList.append(letter)
	position[letter].append(index)
	index += 1
for key in position:
	position[key].insert(0, -1)
	position[key].append(L)
	lm = 0
	for i in range(len(position[key]) - 1):
		length = position[key][i + 1] - position[key][i]
		if length > lm:
			lm = length
	if lm < output:
		output = lm
print(output)


alphavite = 'abcdefghijklmnopqrstyvwxyz'
s = input()
minimal = len(s) + 1
for i in alphavite:
	l = -1
	maxl = 0
	for j in range(len(s)):
		if s[j] == i:
			maxl = max(maxl, j - l)
			l = j
	maxl = max(maxl, len(s) - l)
	minimal = min(minimal, maxl)
print(minimal)


s = str(input())
n = len(s)
ans = 10 ** 18
for i in range(26):
	c = chr(i + ord('a'))
	temp = -1
	p = []
	for j in range(n):
		if s[j] == c:
			p.append(j - temp)
			temp = j
	else:
		p.append(n - temp)
	if p:
		ans = min(ans, max(p))
print(ans)


s = input()
n = len(s)
d = [n + 1] * 26
pre = [-1] * 26
for i in range(n):
	now = ord(s[i]) - ord('a')
	if pre[now] < 0:
		d[now] = i + 1
	else:
		d[now] = max(d[now], i - pre[now])
	pre[now] = i
for i in range(26):
	d[i] = max(d[i], n - pre[i])
print(min(d))


def dominant(s):
	ALPHA_LEN = 26
	pos = [-1] * ALPHA_LEN
	MAX_ = 10000
	ans = len(s) // 2 + len(s) % 2
	dist = [MAX_] * ALPHA_LEN
	for i in range(len(s)):
		idx = ord(s[i]) - ord('a')
		d = i - pos[idx]
		if dist[idx] == MAX_ or d > dist[idx]:
			dist[idx] = d
		pos[idx] = i
	for i in range(ALPHA_LEN):
		d = len(s) - pos[i]
		if d > dist[i]:
			dist[i] = d
	print(min(dist))

def test():
	dominant('abacaba')
	dominant('zzzzz')
	dominant('abcde')
	dominant('abcd')
	dominant('abcded')

def nia():
	s = input()
	while len(s) == 0:
		s = input()
	s = s.split()
	iVal = []
	for i in range(len(s)):
		iVal.append(int(s[i]))
	return iVal

def solve():
	dominant(input())
solve()


s = input()
l = 0
r = len(s)
d = dict()
count = dict()
for i in s:
	d[i] = False
	count[i] = 0
while r - l > 1:
	mid = (r + l) // 2
	for i in s:
		d[i] = False
		count[i] = 0
	for i in range(mid):
		d[s[i]] = True
		count[s[i]] += 1
	for i in range(len(s) - mid):
		count[s[i]] -= 1
		count[s[i + mid]] += 1
		if count[s[i]] == 0:
			d[s[i]] = False
	for i in d.items():
		if i[1]:
			r = mid
	if r != mid:
		l = mid
print(r)


s = input()
letters = list(set(s))
letter_ans = []
for letter in letters:
	index = []
	num = -2
	while num != -1:
		num = s.find(letter, max(0, num + 1))
		index.append(num)
	index.pop()
	max_sub = 0
	for i in range(1, len(index)):
		max_sub = max(index[i] - index[i - 1], max_sub)
	max_sub = max(len(s) - index[-1], max_sub, index[0] + 1)
	letter_ans.append(max_sub)
print(min(letter_ans))


s = input()
sett = set(s)
l = []
for i in sett:
	temp = s
	k = temp.find(i) + 1
	while temp.find(i) != -1:
		temp = temp[temp.find(i) + 1:]
		k = max(k, temp.find(i) + 1)
	if k < len(temp) + 1:
		k = len(temp) + 1
	l.append(k)
print(min(l))


s = input()
n = len(s)
l = [[0] for i in range(26)]
for i in range(len(s)):
	l[ord(s[i]) - 97].append(i + 1)
ans = len(s) // 2 + 1
for i in range(26):
	l[i].append(n + 1)
for i in range(26):
	diff = -10 ** 9
	for j in range(1, len(l[i])):
		diff = max(l[i][j] - l[i][j - 1], diff)
	if diff != -10 ** 9:
		ans = min(ans, diff)
print(ans)


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
s = input()
fa = len(s)
for i in range(26):
	temp = chr(97 + i)
	curr = -1
	ans = -1
	for j in range(len(s)):
		if s[j] == temp:
			tt = j - curr
			ans = max(ans, j - curr)
			curr = j
	ans = max(ans, len(s) - curr)
	fa = min(fa, ans)
print(fa)


line = input()
d = {}
dist = {}
for i in range(len(line)):
	elem = line[i]
	if elem not in d:
		d[elem] = i
		dist[elem] = i + 1
	else:
		dist[elem] = max(dist[elem], i - d[elem])
		d[elem] = i
minimum = 999999999
for key in dist:
	dist[key] = max(dist[key], len(line) - d[key])
	minimum = min(minimum, dist[key])
print(minimum)


import math
s = input()
e = set()
for i in s:
	e.add(i)
d = {}
for i in e:
	d[i] = [-1]
if len(d) == len(s):
	print(math.ceil((len(s) + 1) / 2))
	return
a = []
for i in range(len(s)):
	d[s[i]].append(i)
for i in d:
	d[i].append(len(s))
q = -1
ans = 1221243214
for i in d:
	q = -1
	for j in range(1, len(d[i])):
		q = max(q, d[i][j] - d[i][j - 1])
	ans = min(q, ans)
print(ans)


from collections import defaultdict
s = input()
if len(set(s)) == 1:
	print(1)
elif len(set(s)) == len(s):
	print(len(s) // 2 + 1)
else:
	dist = defaultdict(lambda : (0, 0))
	for (i, c) in enumerate(s):
		if dist[c] == (0, 0):
			dist[c] = (i, i + 1)
		else:
			dist[c] = (i, max(i - dist[c][0], dist[c][1]))
	m = float('inf')
	for k in dist:
		dist[k] = (dist[k][0], max(dist[k][1], len(s) - dist[k][0]))
		if dist[k][1] > float('-inf'):
			m = min(m, dist[k][1])
	print(m)


from functools import reduce
str = input()
main_res = float('inf')
x = {}
for i in str:
	if not i in x:
		arr = list(map(lambda x: len(x), str.split(i)))
		res = reduce(lambda x, y: max([x, y]), arr)
		x[i] = res
		if res < main_res:
			main_res = res
print(main_res + 1)


s = input()
n = len(s)
lst = [-1] * 26
dis = [0] * 26
for i in range(n):
	x = ord(s[i]) - 97
	dis[x] = max(dis[x], i - lst[x])
	lst[x] = i
for i in range(26):
	dis[i] = max(dis[i], n - lst[i])
print(min(dis))


s = input()
pos = {}
gap = {}
res = []
for i in range(len(s)):
	if s[i] not in pos:
		pos[s[i]] = i
		gap[s[i]] = i + 1
	else:
		if i - pos[s[i]] > gap[s[i]]:
			gap[s[i]] = i - pos[s[i]]
		pos[s[i]] = i
for i in gap:
	if len(s) - pos[i] > gap[i]:
		gap[i] = len(s) - pos[i]
for (key, val) in gap.items():
	if s.count(key) > 1:
		res.append(val)
try:
	print(min(min(res), len(s) // 2 + 1))
except:
	print(len(s) // 2 + 1)


s = input()
st = [-1 for i in range(26)]
gap = [0 for i in range(26)]
n = len(s)
for i in range(n):
	r = i - st[ord(s[i]) - 97]
	gap[ord(s[i]) - 97] = max(gap[ord(s[i]) - 97], r)
	st[ord(s[i]) - 97] = i
ans = n
t = 0
for i in gap:
	i = max(i, n - st[t])
	if i != 0:
		ans = min(ans, i)
	t += 1
print(ans)


s = list(input())
c = 97
ans = 999999
for i in range(26):
	pr = -1
	p = 0
	p = chr(c)
	c += 1
	le = -1
	for j in range(len(s)):
		log = True
		if p == s[j]:
			if j - (pr + 1) > le:
				le = j - (pr + 1)
			pr = j
			log = False
		if j == len(s) - 1 and j - pr > le and log:
			le = j - pr
	if ans > le + 1 and le > -1:
		ans = le + 1
print(ans)


from copy import copy
s = input()
alphabet = 'qwertyuioplkjhgfdsazxcvbnm'
anss = len(s)
for sim in alphabet:
	x = copy(s)
	x = x.split(sim)
	ans = 0
	for i in x:
		ans = max(ans, len(i))
	anss = min(anss, ans)
print(anss + 1)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return list(map(str, input().strip()))

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby
from itertools import permutations as comb

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p, d):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	return l
from math import inf
s = S()
n = len(s)
c = set(s)
d = Counter(s)
ans = n
for i in c:
	last = -1
	tmp = 0
	for j in range(n):
		if s[j] == i:
			tmp = max(j - last, tmp)
			last = j
			d[i] -= 1
			if not d[i]:
				tmp = max(n - last, tmp)
				break
	ans = min(tmp, ans)
print(ans)


s = input()
Len = len(s)
min_k = Len
for ch in set(s):
	(last_idx, freq) = (-1, 0)
	for i in range(Len):
		if s[i] == ch:
			freq = max(freq, i - last_idx)
			last_idx = i
	freq = max(freq, Len - last_idx)
	min_k = min(min_k, freq)
print(min_k)


x = input()
lch = []
lln = {}
lin = {}
for i in range(len(x)):
	if x[i] in lch:
		lln[x[i]] = max(lln[x[i]], i - lin[x[i]])
		lin[x[i]] = i
	else:
		lch.append(x[i])
		lln[x[i]] = i + 1
		lin[x[i]] = i
for i in range(len(lch)):
	if lin[lch[i]] != len(x) - 1:
		lln[lch[i]] = max(lln[lch[i]], len(x) - lin[lch[i]])
m = lln[lch[0]]
for i in range(1, len(lch)):
	m = min(m, lln[lch[i]])
print(m)


a = input()
d = 'abcdefghijklmnopqrstuvwxyz'
m = [[-1] for i in range(26)]
n = 0
for i in range(len(a)):
	k = d.index(a[i])
	if len(m[k]) == 1:
		m[k] += [i]
		m[k] += [m[k][1] - m[k][0]]
	else:
		m[k][0] = m[k][1]
		m[k][1] = i
		if m[k][2] < m[k][1] - m[k][0]:
			m[k][2] = m[k][1] - m[k][0]
for i in range(26):
	if len(m[i]) == 3:
		m[i][0] = m[i][1]
		m[i][1] = len(a)
		if m[i][2] < m[i][1] - m[i][0]:
			m[i][2] = m[i][1] - m[i][0]
g = []
j = 0
for i in range(26):
	if len(m[i]) == 3:
		k = a[0:m[i][2]]
		n = a[len(a) - m[i][2]:]
		if k.count(d[i]) > 0 and n.count(d[i]) > 0:
			g += [m[i][2]]
j = len(a) // 2 + 1
if len(g) != 0 and j > min(g):
	print(min(g))
else:
	print(j)


inp = input()
s = set(inp)
n = len(s)
li = []
for x in s:
	seq = inp.split(x)
	maxm = len(seq[0])
	for x in seq:
		maxm = max(maxm, len(x))
	li.append(maxm + 1)
print(min(li))


def main():
	s = input()
	solver(s)

def solver(s):
	n = len(s)
	locs = [-1] * 26
	ks = [n + 1] * 26
	for i in range(n):
		c = s[i]
		ind = index(c)
		k = i - locs[ind]
		locs[ind] = i
		maxK = ks[ind]
		if maxK == n + 1 or k > maxK:
			ks[ind] = k
	for i in range(26):
		k = n - locs[i]
		maxK = ks[i]
		if maxK == n + 1 or k > maxK:
			ks[i] = k
	bestK = min(ks)
	print(bestK)

def index(c):
	return ord(c) - ord('a')
main()


s = input()
hash = dict()
n = len(s)
st = set(list(s))
for i in range(n):
	if s[i] in hash.keys():
		hash[s[i]].append(i + 1)
	else:
		hash[s[i]] = [i + 1]
ans = 1000000
for i in st:
	k = s.rindex(i)
	li = []
	if n - 1 in hash[i] and len(set(list(s))) != 2:
		hash[i].append(n)
	else:
		hash[i].append(n + 1)
	prev = hash[i][0]
	li.append(hash[i][0])
	for l in hash[i][1:]:
		li.append(l - prev)
		prev = l
	m = max(li)
	ans = min(m, ans)
print(ans)


s = list(input())
se = set(s)
mi = 1000000000
if len(se) == len(s):
	mi = len(s) // 2
else:
	for i in se:
		mlo = 0
		lo = 0
		for j in range(len(s)):
			if s[j] != i:
				lo += 1
				if j == len(s) - 1:
					if lo > mlo:
						mlo = lo
						lo = 0
			else:
				if lo > mlo:
					mlo = lo
				lo = 0
		if mlo < mi:
			mi = mlo
print(mi + 1)


s = str(input())
ab = 'abcdefghijklmnopqrstuvwxyz'
ab_ = [0] * 26
answer = [1000000000] * 26
for i in range(26):
	for j in range(len(s)):
		if s[j] == ab[i]:
			ab_[i] += 1
res = 0
for i in range(26):
	if ab_[i] != 0:
		res += 1
if res == 1:
	print(1)
	exit(0)
for sym in range(26):
	positions = [-1]
	delta = 0
	for i in range(len(s)):
		if s[i] == ab[sym]:
			positions.append(i)
	positions.append(len(s))
	if len(positions) > 1:
		for i in range(len(positions) - 1):
			if positions[i + 1] - positions[i] > delta:
				delta = positions[i + 1] - positions[i]
	if delta > 0:
		answer[sym] = delta
print(min(answer))


d = dict()
s = input()
for i in set(s):
	a = s.index(i)
	d[i] = [a + 1, a]
p = 0
for j in range(len(s)):
	i = s[j]
	d[i][0] = max(d[i][0], j - d[i][1])
	d[i][1] = j
ans = len(s)
k = len(s)
for i in d.values():
	if i[0] != 0:
		ans = min(ans, max(i[0], k - i[1]))
print(ans)


s = input()
letters = set(s)
p = dict.fromkeys(letters, [-1, -1])
for (i, c) in enumerate(s):
	u = max(p[c][1], i - p[c][0])
	p[c] = [i, u]
for value in p.values():
	value[1] = max(len(s) - value[0], value[1])
print(min((i[1] for i in p.values() if i[1] != -1)))


import collections
s = input()
ctr = collections.Counter(s)
ctrk = ctr.keys()
print(min([max(map(len, s.split(c))) + 1 for c in ctrk]))


s = input()
print(min((max(map(len, s.split(i))) + 1 for i in list(set(s)))))


a = input()
n = len(a)
ans = -1
for i in range(26):
	c = chr(97 + i)
	last = -1
	tmp = 0
	for i in range(n):
		if a[i] == c:
			tmp = max(tmp, i - last)
			last = i
	tmp = max(tmp, n - last)
	if ans == -1:
		ans = tmp
	else:
		ans = min(ans, tmp)
print(ans)


import sys, math
s = input()
n = len(s)
a = [[0] for i in range(26)]
for i in range(n):
	a[ord(s[i]) - 97].append(i + 1)
for i in range(26):
	a[i].append(n + 1)
ans = n + 1
for i in range(26):
	cur = 0
	for j in range(1, len(a[i])):
		cur = max(cur, a[i][j] - a[i][j - 1])
	ans = min(ans, cur)
print(ans)


string = input()
k = 1000000
for c in range(ord('a'), ord('z') + 1):
	c = chr(c)
	kc = 0
	length = 0
	for i in range(0, len(string)):
		if string[i] == c:
			kc = max([kc, length])
			length = 0
		else:
			length += 1
	kc = max([kc, length])
	k = min([kc, k])
print(k + 1)


s = input()
n = len(s)
a = [-1] * 26
b = [0] * 26
for i in range(n):
	tmp = ord(s[i]) - 97
	b[tmp] = max(b[tmp], i - a[tmp])
	a[tmp] = i
for i in range(26):
	b[i] = max(b[i], n - a[i])
print(min(b))


import string
s = input()

def max_dist(s, c):
	pos = [-1]
	for (i, val) in enumerate(s):
		if val == c:
			pos.append(i)
	pos.append(len(s))
	return max((pos[i + 1] - pos[i] for i in range(len(pos) - 1)))
print(min((max_dist(s, c) for c in string.ascii_lowercase)))


s = input()
n = len(s)
min1 = n + 1
for i in range(26):
	initial = -1
	max2 = 0
	for j in range(n):
		if ord(s[j]) - ord('a') == i:
			max2 = max(max2, j - initial)
			initial = j
	max2 = max(max2, n - initial)
	if initial != -1:
		min1 = min(min1, max2)
print(min1)


s = input()
r = 100000
l = 0
dictC = {}
setC = set()
for i in range(97, 97 + 26):
	setC.add(chr(i))
	dictC.update({chr(i): 0})

def seach(k, setC, dict1):
	for i in range(0, len(s)):
		dict1[s[i]] += 1
		if i >= k - 1:
			if i != k - 1:
				dict1[s[i - k]] -= 1
			set2 = set()
			for z in setC:
				if dict1[z] != 0:
					set2.add(z)
			setC = set2
			if len(setC) == 0:
				return 0
	return 1
while r - l > 1:
	mid = (r + l) // 2
	for i in range(97, 97 + 26):
		dictC.update({chr(i): 0})
	if seach(mid, setC, dictC) == 1:
		r = mid
	else:
		l = mid
print(r)


import sys
import math
from collections import defaultdict

def search(s, n, l):
	rec = [0] * 26
	for i in range(l + 1):
		rec[ord(s[i]) - 97] += 1
	(i, j) = (0, l)
	while j != n - 1:
		j += 1
		rec[ord(s[j]) - 97] += 1 if rec[ord(s[j]) - 97] > 0 else 0
		rec[ord(s[i]) - 97] -= 1
		i += 1
	for i in range(26):
		if rec[i] > 0:
			return True
	return False

def solve(test):
	s = list(input())
	n = len(s)
	if len(set(s)) == 1:
		print(1)
		return
	start = 0
	end = n - 1
	ans = n
	while start <= end:
		mid = (start + end) // 2
		if search(s, n, mid):
			ans = min(ans, mid + 1)
			end = mid - 1
		else:
			start = mid + 1
	print(ans)
test_cases = 1
for t in range(1, test_cases + 1):
	solve(t)


import string
s = input()
d = {x: [0, -1] for x in string.ascii_lowercase}
for i in range(len(s)):
	d[s[i]][0] = max(i - d[s[i]][1], d[s[i]][0])
	d[s[i]][1] = i
a = []
for i in d:
	d[i][0] = max(len(s) - d[i][1], d[i][0])
	a.append(d[i][0])
a.sort()
print(a[0])


s = input()
import string
dct = {ch: -1 for ch in string.ascii_lowercase}
distances = {ch: [] for ch in string.ascii_lowercase}
for (i, ch) in enumerate(s):
	distances[ch].append(i - dct[ch])
	dct[ch] = i
dct = {ch: -1 for ch in string.ascii_lowercase}
distances_backward = {ch: [] for ch in string.ascii_lowercase}
for (i, ch) in enumerate(s[::-1]):
	distances_backward[ch].append(i - dct[ch])
	dct[ch] = i
ans = 10 ** 9
for ch in set(s):
	m1 = max(distances[ch])
	m2 = max(distances_backward[ch])
	m = max(m1, m2)
	if m < ans:
		ans = m
print(ans)


s = input()
alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
ans = 1000000
for i in alpha:
	occ = []
	for j in range(len(s)):
		if s[j] == i:
			occ.append(j)
	occ.append(len(s))
	diff = []
	st = 0
	for k in occ:
		diff.append(k - st)
		st = k
	diff[0] += 1
	z = max(diff)
	ans = min(max(diff), ans)
print(ans)


a = input()
l = len(a)
from collections import defaultdict
b = defaultdict(list)
for i in range(l):
	b[ord(a[i]) - 97].append(i)
p = []
for z in b:
	i = b[z]
	k = len(i)
	d = []
	d.append(i[0] + 1)
	for j in range(1, k):
		d.append(i[j] - i[j - 1])
	d.append(l - i[k - 1])
	p.append(max(d))
print(min(p))


def possible(s, k):
	candidates = set(s[:k])
	count = {}
	for c in s[:k]:
		if c not in count:
			count[c] = 0
		count[c] += 1
	for i in range(k, len(s)):
		count[s[i - k]] -= 1
		if s[i] not in count:
			count[s[i]] = 0
		count[s[i]] += 1
		if count[s[i - k]] == 0 and s[i - k] in candidates:
			candidates.remove(s[i - k])
	return len(candidates) > 0

def bs(s):
	L = 1
	R = len(s)
	while R - L > 1:
		M = (L + R) // 2
		if possible(s, M):
			R = M
		else:
			L = M
	for ans in range(L, R + 1):
		if possible(s, ans):
			return ans
	return -1
print(bs(input()))


import os
import sys
from io import BytesIO, IOBase

def main():
	s = input()
	p = set(list(s))
	ans = 99999999999999999999999
	for x in p:
		ans = min(ans, max(list(map(len, s.split(x)))))
	print(ans + 1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


s = '!' + input()
m = set(s)
d = {}
d1 = {}
for x in range(1, len(s)):
	if not s[x] in d:
		d[s[x]] = x
	else:
		d[s[x]] = max(d[s[x]], x - s[:x].rindex(s[x]))
	d1[s[x]] = x
for (x, y) in list(d.items()):
	d[x] = max(d[x], len(s) - d1[x])
print(min(d.values()))


s = input().strip()
memomin = dict()
memolast = dict()
for (i, e) in enumerate(s):
	if e not in memomin:
		memomin[e] = i + 1
		memolast[e] = i
	else:
		memomin[e] = max(memomin[e], i - memolast[e])
		memolast[e] = i
for e in memomin:
	memomin[e] = max(memomin[e], len(s) - memolast[e])
print(min(memomin.values()))


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
s = si()
n = len(s)
mn = n + 10
for i in 'abcdefghijklmnopqrstuvwxyz':
	pi = 0
	mx = 0
	for j in range(n):
		if s[j] == i:
			mx = max(mx, j - pi + 1)
			pi = j + 1
	mx = max(mx, n - pi + 1)
	mn = min(mn, mx)
print(mn)


S = input()
dp = [[1 for i in range(26)] for j in range(len(S))]
for i in range(len(S) - 2, -1, -1):
	dp[i] = [x + 1 for x in dp[i + 1]]
	dp[i][ord(S[i + 1]) - ord('a')] = 1
dp2 = [[1 for i in range(26)] for j in range(len(S))]
for i in range(1, len(S)):
	dp2[i] = [x + 1 for x in dp2[i - 1]]
	dp2[i][ord(S[i - 1]) - ord('a')] = 1
ans = [0 for i in range(26)]
for i in range(len(S)):
	k = ord(S[i]) - ord('a')
	ans[k] = max(ans[k], dp[i][k], dp2[i][k])
out = len(S)
for i in range(26):
	if ans[i]:
		out = min(out, ans[i])
print(out)


word = input()
n = len(word)
(d, e) = ({}, {})
for i in range(n):
	if word[i] in d:
		d[word[i]].append(i + 1)
	else:
		e[word[i]] = 0
		d[word[i]] = [i + 1]
for i in d:
	temp = d[i]
	if len(temp) == 1:
		cnt = temp[0]
		cnt = max(n - temp[0] + 1, cnt)
		e[i] = cnt
	else:
		cnt = -1
		for j in range(1, len(temp)):
			cnt = max(cnt, temp[j] - temp[j - 1])
		cnt = max(temp[0], cnt)
		cnt = max(cnt, n - temp[-1] + 1)
		e[i] = cnt
ans = 10 ** 10
for i in e:
	ans = min(e[i], ans)
print(ans)


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
s = input()
Ans = float('inf')
for i in range(97, 123):
	t = -1
	maxi = 0
	for j in range(len(s)):
		if s[j] == chr(i):
			maxi = max(maxi, j - t)
			t = j
	maxi = max(maxi, len(s) - t)
	Ans = min(Ans, maxi)
print(Ans)


inp = lambda : map(int, input().split())
s = input()
l = len(s)
lab = [0] * 27
m = [-1] * 27
for i in range(27):
	fl = 0
	d = 0
	for j in range(l):
		if s[j] == chr(i + ord('a')):
			fl = 1
			break
	k = j
	if fl == 0:
		continue
	fl = 0
	for j in range(k + 1, l):
		if s[j] != chr(i + ord('a')):
			d += 1
		else:
			fl = 1
			m[i] = max(m[i], d + 1)
			d = 0
			last = j
	if fl == 0:
		m[i] = max(k + 1, l - k)
	else:
		m[i] = max(m[i], k + 1, l - last)
r = 10000000
for i in range(27):
	if m[i] >= 0:
		r = min(r, m[i])
print(r)


import sys
input = sys.stdin.readline
from collections import defaultdict

def judge(x):
	cnt = [0] * 26
	for i in range(x):
		cnt[d[s[i]]] += 1
	flag = [True] * 26
	for i in range(26):
		if cnt[i] == 0:
			flag[i] = False
	for i in range(x, len(s)):
		cnt[d[s[i]]] += 1
		cnt[d[s[i - x]]] -= 1
		for j in range(26):
			if cnt[j] == 0:
				flag[j] = False
	return True in flag

def binary_search():
	(l, r) = (1, len(s))
	while l <= r:
		mid = (l + r) // 2
		if judge(mid):
			r = mid - 1
		else:
			l = mid + 1
	return l
s = input()[:-1]
alpha = 'abcdefghijklmnopqrstuvwxyz'
d = defaultdict(int)
for i in range(26):
	d[alpha[i]] = i
print(binary_search())


s = input()
ans = len(s) // 2 + 1
p = [-1] * 26
d = [-1] * 26
for i in range(len(s)):
	t = ord(s[i]) - ord('a')
	d[t] = max(d[t], i - p[t])
	p[t] = i
for i in range(26):
	if p[i] < 0:
		continue
	d[i] = max(d[i], len(s) - p[i])
	ans = min(ans, d[i])
print(ans)


s = input()
t = sorted(list(set(s)))
a1 = []
for k in t:
	(t1, dk) = ([], 0)
	for i in range(len(s)):
		if s[i] == k:
			t1.append(i + 1 - dk)
			dk = i + 1
	t1.append(len(s) + 1 - dk)
	a1.append(max(t1))
print(min(a1))


s = input()
s1 = set()
for i in s:
	s1.add(i)
l1 = list(s1)
an = len(s)
for i in l1:
	st = -1
	mx = 0
	for j in range(len(s)):
		if s[j] == i:
			mx = max(mx, j - st)
			st = j
	mx = max(mx, len(s) - st)
	an = min(an, mx)
print(an)


s = input()
ll = l = len(s)
for i in range(26):
	d = chr(i + ord('a'))
	t = 0
	if d in s:
		ll = 0
		for i in s:
			t += 1
			if i == d:
				ll = max(t, ll)
				t = 0
		t += 1
		ll = max(t, ll)
	l = min(ll, l)
print(l)


import math
import heapq
from collections import defaultdict, deque
from decimal import *

def r():
	return int(input())

def rm():
	return map(int, input().split())

def rl():
	return list(map(int, input().split()))
s = input()
a = [[] for i in range(26)]
n = len(s)
for i in range(n):
	a[ord(s[i]) - 97].append(i)
res = math.inf
for k in range(26):
	b = a[k]
	temp = -math.inf
	nb = len(b)
	if nb == 0:
		continue
	if nb == 1:
		temp = max(b[0] + 1, n - b[0])
	else:
		for (i, j) in enumerate(b):
			if i == 0:
				temp = max(temp, b[i] + 1)
				temp = max(temp, b[i + 1] - b[i])
			elif i == nb - 1:
				temp = max(temp, b[i] - b[i - 1])
				temp = max(temp, n - b[i])
			else:
				temp = max(temp, b[i] - b[i - 1])
				temp = max(temp, b[i + 1] - b[i])
	res = min(res, temp)
print(res)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
S = input()

def check(s, k):
	for w in set(s):
		c = s[:k].count(w)
		if c == 0:
			continue
		for i in range(k, len(s)):
			if s[i - k] == w:
				c -= 1
			if s[i] == w:
				c += 1
			if c == 0:
				break
		if c > 0:
			return True
	return False
lo = 1
hi = len(S)
while lo < hi:
	m = (lo + hi) // 2
	if check(S, m):
		hi = m
	else:
		lo = m + 1
print(lo)


import string
s = input()
les = len(s)
ans = les
for c in string.ascii_lowercase:
	(l, a) = (-1, 0)
	for i in range(les):
		if s[i] == c:
			a = max(a, i - l)
			l = i
	a = max(a, les - l)
	ans = min(ans, a)
print(ans)


string = input()
count = {}
prev_index = {}
for i in range(len(string)):
	current = string[i]
	if current in count:
		count[current] = max(count[current], i - prev_index[current])
	else:
		count[current] = i + 1
	prev_index[current] = i
for i in string:
	count[i] = max(count[i], len(string) - prev_index[i])
print(min(count.values()))


import string
n = input()
l = len(n)
dist = {x: 0 for x in string.ascii_lowercase}
last = {x: -1 for x in string.ascii_lowercase}
for i in range(l):
	dist[n[i]] = max(dist[n[i]], i - last[n[i]])
	last[n[i]] = i
for i in dist.keys():
	dist[i] = max(dist[i], l - last[i])
print(min(dist.values()))


s = input()
A = set()
for i in s:
	A.add(i)
Range = {}
for item in A:
	key = s.find(item)
	Range[item] = key + 1
	for i in range(key + 1, len(s)):
		if s[i] == item:
			if i - key > Range[item]:
				Range[item] = i - key
			key = i
	if len(s) - key > Range[item]:
		Range[item] = len(s) - key
min = 1000000000
for item in Range.values():
	if item < min:
		min = item
print(min)


s = input()
prev = [-1] * 26
dist = [0] * 26
n = len(s)
for i in range(n):
	ch = ord(s[i]) - ord('a')
	dist[ch] = max(dist[ch], i - prev[ch])
	prev[ch] = i
for i in range(26):
	dist[i] = max(dist[i], n - prev[i])
print(min(dist))


s = input()
t = set(s)
t = list(t)

def verif(c, s, k):
	compt = 0
	for i in range(len(s)):
		compt += 1
		if c == s[i]:
			compt = 0
		if compt == k:
			return False
	return True
v = []
right = len(s)
left = 0
while right - left > 1:
	mid = (right + left) // 2
	if verif(t[0], s, mid):
		right = mid
	else:
		left = mid
v.append(right)
for i in range(1, len(t)):
	if verif(t[i], s, min(v) - 1):
		left = 0
		right = min(v)
		while right - left > 1:
			mid = (right + left) // 2
			if verif(t[i], s, mid):
				right = mid
			else:
				left = mid
		v.append(right)
print(min(v))


a = input()
S = [[-1] for i in range(26)]
for i in range(len(a)):
	S[ord(a[i]) % 97] += [i]
for i in range(len(S)):
	S[i] += [len(a)]
min = [-1 for i in range(26)]
for i in range(26):
	for j in range(1, len(S[i])):
		if min[i] < S[i][j] - S[i][j - 1]:
			min[i] = S[i][j] - S[i][j - 1]
m = 10 ** 6
for i in min:
	if i != -1 and i < m:
		m = i
print(m)


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
s = minp()
a = [-1] * 26
M = [0] * 26
for i in range(len(s)):
	z = ord(s[i]) - ord('a')
	M[z] = max(M[z], i - a[z])
	a[z] = i
for i in range(26):
	M[i] = max(M[i], len(s) - a[i])
print(min(M))


import itertools
import bisect
import math
from collections import *
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def main():
	s = li()
	n = len(s)
	d = defaultdict(list)
	for i in range(n):
		d[s[i]].append(i)
	s = sorted(set(s))
	pp = sys.maxsize
	for i in range(len(s)):
		lst = [-1]
		lst.extend(list(d[s[i]]))
		lst.append(n)
		ans = 0
		for j in range(1, len(lst)):
			ans = max(ans, lst[j] - lst[j - 1])
		pp = min(ans, pp)
	print(pp)
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


Str = input()
Ln = len(Str)
lastIndex = {}
maxDist = {}
for i in range(Ln):
	if not Str[i] in lastIndex:
		lastIndex[Str[i]] = i
		maxDist[Str[i]] = i + 1
	else:
		maxDist[Str[i]] = max(maxDist[Str[i]], i - lastIndex[Str[i]])
		lastIndex[Str[i]] = i
for i in lastIndex:
	maxDist[i] = max(Ln - lastIndex[i], maxDist[i])
Min = -1
for i in maxDist:
	if Min == -1 or maxDist[i] < Min:
		Min = maxDist[i]
print(Min)


s = str(input())
set_str = set(s)
distance = []
for i in set_str:
	distance.append(max(map(len, s.split(i))))
print(min(distance) + 1)


s = input()
c = dict.fromkeys(list('abcdefghijklmnopqrstuvwxyz'), -1)
r = dict.fromkeys(list('abcdefghijklmnopqrstuvwxyz'), 0)
for i in range(len(s)):
	a = s[i]
	x = i - c[a]
	if x > r[a]:
		r[a] = x
	c[a] = i
d = len(s)
for i in c.keys():
	x = d - c[i]
	if x > r[i]:
		r[i] = x
d = min(r.values())
print(d)


from sys import stdin

def main():
	s = stdin.readline()
	size = len(s) - 1
	ans = size
	for i in range(26):
		low = 0
		high = size
		curr_ch = i
		while low < high:
			mid = (low + high) // 2
			count = 0
			for j in range(mid):
				if ord(s[j]) - ord('a') == curr_ch:
					count += 1
			if count == 0:
				ok = False
			else:
				ok = True
				for j in range(mid, size):
					if ord(s[j - mid]) - ord('a') == curr_ch:
						count -= 1
					if ord(s[j]) - ord('a') == curr_ch:
						count += 1
					if count == 0:
						ok = False
						break
			if ok:
				high = mid
			else:
				low = mid + 1
		ans = min(ans, low)
	print(ans)
main()


def check(s, K):
	for ch in range(0, 26):
		c = chr(97 + ch)
		last = -1
		found = True
		for i in range(0, K):
			if s[i] == c:
				last = i
		if last == -1:
			continue
		for i in range(K, len(s)):
			if s[i] == c:
				last = i
			if last <= i - K:
				found = False
				break
		if found:
			return 1
	return 0

def binarySearch(s):
	(low, high, ans) = (1, len(s), None)
	while low <= high:
		mid = high + low >> 1
		if check(s, mid):
			(ans, high) = (mid, mid - 1)
		else:
			low = mid + 1
	return ans
s = input()
print(binarySearch(s))


s = input()
n = len(s)
l = 0
r = n + 1
while r - l > 1:
	m = (l + r) // 2
	t = set(s[:m])
	d = {}
	for i in range(m):
		if s[i] in d:
			d[s[i]] += 1
		else:
			d[s[i]] = 1
	for i in range(m, n):
		if s[i] in t:
			d[s[i]] += 1
		if s[i - m] in t:
			d[s[i - m]] -= 1
			if d[s[i - m]] == 0:
				t.remove(s[i - m])
	if len(t) > 0:
		r = m
	else:
		l = m
print(r)


s = input()
c = float('Inf')
for chr in set(s):
	l = 0
	for j in s.split(chr):
		l = max(l, len(j))
	c = min(l, c)
print(c + 1)


def lc(string):
	ans = 1000000000
	real = {}
	fake = {}
	i = 0
	for x in string:
		if x not in fake:
			fake[x] = i
			real[x] = max(real.get(x, 0), i + 1)
		else:
			val = i - fake.get(x, 0)
			fake[x] = i
			real[x] = max(real.get(x, 0), val)
		i += 1
	for x in real:
		val = len(string) - fake.get(x, 0)
		fake[x] = i
		real[x] = max(real.get(x, 0), val)
	for x in real:
		ans = min(ans, real[x])
	else:
		return ans
print(lc(input()))


string = input()
previous = []
distances = []
for i in range(26):
	previous.append(-1)
	distances.append(-1)
for (count, i) in enumerate(string):
	num = ord(i) - 97
	currDist = count - previous[num]
	distances[num] = max(currDist, distances[num])
	previous[num] = count
for num in range(26):
	count = len(string)
	currDist = count - previous[num]
	distances[num] = max(currDist, distances[num])
print(min(distances))


import collections
s = input()
chars = collections.Counter(s).keys()
print(min((max(map(len, s.split(c))) + 1 for c in chars)))


from sys import stdin, stdout
from collections import Counter
from collections import defaultdict
from math import ceil
from bisect import bisect_left
from bisect import bisect_right
import math
ai = lambda : list(map(int, stdin.readline().split()))
ei = lambda : map(int, stdin.readline().split())
ip = lambda : int(stdin.readline().strip())
s = input()
ans = []
for i in list(set(s)):
	ans += (max(map(len, s.split(i))) + 1,)
print(min(ans))


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def lcm(x, y):
	return x * y / gcd(x, y)

def fact(x, mod=mod):
	ans = 1
	for i in range(1, x + 1):
		ans = ans * i % mod
	return ans

def arr2D(n, m, default=0):
	lst = []
	for i in range(n):
		temp = [default] * m
		lst.append(temp)
	return lst

def sortDictV(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

def isValid(n, s, k):
	for j in range(97, 123):
		end = False
		letter = chr(j)
		cnt = s[:k].count(letter)
		if cnt == 0:
			continue
		for i in range(1, n - k + 1):
			if s[i - 1] == letter:
				cnt -= 1
			if s[i + k - 1] == letter:
				cnt += 1
			if cnt == 0:
				end = True
				break
		if end:
			continue
		return 1
	return 0

def solve(s):
	n = len(s)
	(l, h) = (0, n)
	mid = 0
	while l < h - 1:
		mid = (l + h) // 2
		if isValid(n, s, mid):
			h = mid
		else:
			l = mid
	if isValid(n, s, l):
		return l
	else:
		return h
s = list(input())
print(solve(s))


def f(c):
	return ord(c) - ord('a')

def main():
	s = input() + '#'
	k = [0 for i in range(26)]
	w = [1 for i in range(26)]
	for i in range(len(s)):
		for j in range(26):
			if s[i] == '#' or f(s[i]) == j:
				k[j] = max(k[j], w[j])
				w[j] = 1
			else:
				w[j] += 1
	print(min(*k))
main()


from sys import stdin, exit, setrecursionlimit
from collections import deque
input = stdin.readline
lmi = lambda : list(map(int, input().split()))
mi = lambda : map(int, input().split())
si = lambda : input().strip('\n')
ssi = lambda : input().strip('\n').split()
mod = 10 ** 9 + 7

def check(k):
	ok = [False for i in range(26)]
	cnt = [0 for i in range(26)]
	for i in range(k):
		ok[ord(s[i]) - ord('a')] = True
		cnt[ord(s[i]) - ord('a')] += 1
	for i in range(k, len(s)):
		cnt[ord(s[i]) - ord('a')] += 1
		cnt[ord(s[i - k]) - ord('a')] -= 1
		if cnt[ord(s[i - k]) - ord('a')] == 0:
			ok[ord(s[i - k]) - ord('a')] = False
	for i in ok:
		if i:
			return True
	return False
s = si()
l = 0
r = len(s)
while l < r:
	mid = l + r >> 1
	if check(mid):
		r = mid
	else:
		l = mid + 1
print(l)


s = input()
abc = list(set(s))
ans = 100000000000
for i in abc:
	ans = min(max(map(len, s.split(i))) + 1, ans)
print(ans)