C. К-доминирующий символ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка s, состоящая из строчных латинских букв. Символ c называется k-доминирующим, когда каждая подстрока s длины не меньше k содержит символ c.

Найдите минимальное значение k такое, что в строке существует хотя бы один k-доминантный символ.

Входные данные

Первая строка — строка s, состоящая из строчных латинских букв (1 ≤ |s| ≤ 100000).

Выходные данные

Выведите одно число — минимальное значение k такое, что в строке существует хотя бы один k-доминантный символ.

Примеры
Входные данные
abacaba
Выходные данные
2
Входные данные
zzzzz
Выходные данные
1
Входные данные
abcde
Выходные данные
3