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.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.SortedMap;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

  public class Test
 {
    static PrintWriter pw = new PrintWriter(System.out);
    static ArrayList<Integer>[] ar = new ArrayList[26];
    static int n;
    static boolean check(int x)
    {
        for(int i = 0 ; i<26 ;i++)
        {
            int size = ar[i].size();
            if(size == 0)continue;
            
            int a = ar[i].get(0) - 0 + 1;
            int b = n - 1 - ar[i].get(size - 1) + 1;
            
            a = Math.max(a, b);
            if(a > x && a != 1)continue;
            
            boolean okey = true;
            for(int j = 0 ; j<size-1 ; j++)
            {
                int t1 = ar[i].get(j);
                int t2 = ar[i].get(j+1);
                int temp = t2 - t1;
                if(temp > x)
                {
                    okey = false;
                    break;
                }
                
            }
            if(okey)
            {
                return true;
            }
           
        }
        
        return false;
    }
    public static void main(String[] args)throws Exception
    {
        Reader.init(System.in);
        String s = Reader.next();
        n = s.length();
        
        for(int i = 0 ; i<26 ; i++)
            ar[i] = new ArrayList();
        
        for(int i = 0 ; i<n ; i++)
        {
            ar[s.charAt(i) - 'a'].add(i);
        }
        
        int L = 1 , R = n , res = (int)1e6;
        while(L<=R)
        {
            int mid = (L+R)/2;
            if(check(mid))
            {
                res = mid;
                R = mid - 1;
            }
            else
                L = mid + 1;
            
        }
        
        pw.print(res);
        pw.close();
    }
    
  }
  


class Reader {

    static BufferedReader reader;
    static StringTokenizer tokenizer;

    public static int pars(String x) {
        int num = 0;
        int i = 0;
        if (x.charAt(0) == '-') {
            i = 1;
        }
        for (; i < x.length(); i++) {
            num = num * 10 + (x.charAt(i) - '0');
        }

        if (x.charAt(0) == '-') {
            return -num;
        }

        return num;
    }

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static void init(FileReader input) {
        reader = new BufferedReader(input);
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return pars(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}