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.util.*;
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
 
public class Es
{
	static class P implements Comparable
	{
		int first;
		int second;
		
		public P(int f, int s)
		{
			first = f;
			second = s;
		}
		
		public String toString()
		{
			return first + " " + second;
		}
		
		public int compareTo(Object o)
		{
			P p2 = (P)o;
			if(this.first - this.second > p2.first - p2.second)
				return -1;
			if(this.first - this.second < p2.first - p2.second)
				return 1;
			return 0;
		}
	}
	
	static int log2(double a)
	{
		return (int)(Math.log(a) / Math.log(2));
	}
	
	static long gcd(long a, long b)
	{
		long r;
		while((r = a % b) > 0)
		{
			a = b;
			b = r;
		}
		return b;
	}
	
	public static void main(String[] args) throws IOException
	{
		char[] v = in.next().toCharArray();
		int[][] m = new int[200][2];
		int ans = Integer.MAX_VALUE;
		for(int i = 0; i < v.length; i ++)
		{
			m[v[i]][1] = Math.max(m[v[i]][1], i - m[v[i]][0] + (m[v[i]][1] == 0 ? 1 : 0));
			m[v[i]][0] = i;
		}
		for(int i = 0; i < m.length; i ++)
		{
			m[i][1] = Math.max(m[i][1], v.length - m[i][0]);
		}
		for(int i = 0; i < v.length; i ++)
		{
			//sop(v[i] + " " + m[v[i]][1] + "\n");
			ans = Math.min(m[v[i]][1], ans);
		}
		sop(ans);
	}
    
	static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
	
    static FastReader in = new FastReader();
  
    public static void sop(Object o)
    {
    	System.out.print(o);
    }
}