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.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public
class TaskC {
    //static variable
    static  int v=0;
    static final int mod = (int) 1e9 + 7;
    static final double eps = 1e-6;
    static final double pi = Math.PI;
    static final long inf = Long.MAX_VALUE / 2;




    BufferedReader br;
    void main1() throws IOException {
        br=new BufferedReader(new InputStreamReader(System.in));
        String s=si();
        ArrayList[] al=new ArrayList[26];
        for (int i = 0; i <al.length ; i++) {
            al[i]=new ArrayList();
        }
        Set<Character> set=new HashSet();
        for (int i = 0; i <s.length() ; i++) {
            if(al[s.charAt(i)-97].size()==0)
                al[s.charAt(i)-97].add(-1);
            al[s.charAt(i)-97].add(i);
            set.add(s.charAt(i));
        }
        int n=s.length();
        for (char ss:set) {
            al[ss-97].add(n);
            //System.out.println(al[ss-97]);
        }
        //System.out.println();
        int max=Integer.MAX_VALUE;
        for (int i = 0; i <26 ; i++) {
            if(al[i].size()<=3)
                continue;

            int min=Integer.MIN_VALUE;
            for (int j = 1; j <al[i].size() ; j++) {
                int diff=Math.abs((int)al[i].get(j)-(int)al[i].get(j-1));
                if(diff>min)
                    min=diff;

            }
            if(min<max)
                max=min;
        }
        int ans;
        if(n%2==0)
           ans=(n/2)+1;
        else
            ans=(n+1)/2;


        if (ans>max)
         System.out.println(max);
        else
            System.out.println(ans);
    }













    //Main Method............................................................................................................
    public static void main(String[] args) throws IOException {new TaskC().main1();}

    //input method
    int[] iint() throws IOException{
        String line[]=br.readLine().split(" ");
        int[] a=new int[line.length];
        for (int i=0;i<line.length ;i++ ) {
            a[i]=Integer.parseInt(line[i]);
        }
        return a;
    }
    long[] ilong() throws IOException{
        String line[]=br.readLine().split(" ");
        long[] a=new long[line.length];
        for (int i=0;i<line.length ;i++ ) {
            a[i]=Long.parseLong(line[i]);
        }
        return a;
    }
    double[] idouble() throws IOException{
        String line[]=br.readLine().split(" ");
        double[] a=new double[line.length];
        for (int i=0;i<line.length ;i++ ) {
            a[i]=Long.parseLong(line[i]);
        }
        return a;
    }
    long li() throws IOException{

        return Long.parseLong(br.readLine());
    }
    int ii() throws IOException{

        return Integer.parseInt(br.readLine());
    }
    double di() throws IOException{
        return Double.parseDouble(br.readLine());
    }
    char ci() throws IOException{
        return (char)br.read();
    }
    String si() throws IOException{
        return br.readLine();
    }
    String[] isa(int n) throws IOException{
        String at =si();
        return at.split(" ");
    }

    double[][] idm(int n, int m) throws IOException{
        double a[][] = new double[n][m];
        for (int i = 0; i < n; i++) {
            double[] temp=idouble();
            for (int j = 0; j < m; j++) a[i][j] = temp[j];
        }
        return a;
    }

    int[][] iim(int n, int m) throws IOException{
        int a[][] = new int[n][m];
        for (int i = 0; i < n; i++) {
            int[] temp=iint();
            for (int j = 0; j < m; j++) a[i][j] =temp[j];
        }
        return a;
    }
    long[][] ilm(int n, int m) throws IOException{
        long a[][] = new long[n][m];
        for (int i = 0; i < n; i++) {
            long[] temp=ilong();
            for (int j = 0; j < m; j++) a[i][j] =temp[j];
        }
        return a;
    }

}