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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

/**
 * Created by first on 7/21/2018.
 */
public class K_DominantCharacter_C {
    public static void main(String [] args){
        K_DominantCharacter_C x = new K_DominantCharacter_C();
        x.solve();
    }
    public void solve() {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));
        String st = "";
        try {
            st = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
        int length = st.length();
        for (int i = 0; i < length; i++) {
            if (map.get(st.charAt(i)) == null) {
                ArrayList<Integer> arr = new ArrayList<>();
                arr.add(i);
                map.put(st.charAt(i), arr);
            } else {
                map.get(st.charAt(i)).add(i);
            }
        }
        char c = 'a';
        int minOfMax = Integer.MAX_VALUE;
        for (int i = 0; i < 26; i++) {
            ArrayList<Integer> arr = map.get(c);
            if (arr != null) {
                int Max = arr.get(0)+1;

                for (int j = 0; j < arr.size() - 1 && arr.get(0) < minOfMax && length - arr.get(arr.size()-1) <= minOfMax; j++) {
                    if (arr.get(j + 1) - arr.get(j) > Max) {
                        Max = arr.get(j + 1) - arr.get(j);
                    }
                }
                if(length - arr.get(arr.size()-1) > Max){
                    Max = length - arr.get(arr.size()-1);
                }
                if (Max < minOfMax && Max != Integer.MIN_VALUE) {
                    minOfMax = Max;
                }
            }
            c = (char) (c + 1);
        }
        if (minOfMax != Integer.MAX_VALUE){
            System.out.println(minOfMax);
        } else {
            System.out.println(length/2 + 1);
        }
        /*int counter = 1;
        int output = (length+1)/2;
        char firstChar = st.charAt(length/2);
        char secondChar = st.charAt(length/2 - 1);
        boolean isFirst = false;
        boolean isFirstRight = true;
        boolean isSecondRight = true;
        boolean isSecond = true;
        for(int i = length/2 - 1; i >= 0; i--){
            if(i+2*counter < length){
                if((st.charAt(i) == firstChar && firstChar == st.charAt(i+2*counter) && isFirst) ||
                        (st.charAt(i) == secondChar && secondChar == st.charAt(i+2*counter) && isSecond)) {
                    output = (length + 1) / 2 + - counter ;
                    counter++;

                }else if((!(st.charAt(i) == firstChar && firstChar == st.charAt(i+2*counter)) && isFirst)){
                    isFirstRight = false;
                }else if((!(st.charAt(i) == secondChar && secondChar == st.charAt(i+2*counter)) && isSecond)) {
                    isSecondRight = false;
                }
                isFirst = !isFirst && isFirstRight;
                isSecond = !isSecond && isSecondRight;
            }
        }
        if(output == 1) {
            if(firstChar == secondChar) {
                System.out.println(output);
            }else{
                System.out.println(2);
            }
        } else {
            System.out.println(output);
        }
    */
    }
}
