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.io.PrintWriter;
import java.util.*;
 
public class Solution {
	public static void main(String[] args) {
		InputReader in = new InputReader();
		PrintWriter out = new PrintWriter(System.out);
		Thread th = new Thread(null, new Runnable(){public void run(){new Task1().solve(in, out);}},"Task1",1<<24);
		try{
			th.start();
			th.join();
		} catch(InterruptedException e){}
		out.close();
	}
	
	static class Task1 {
		static final int MAX = 1000001;
		static final int MOD = 1000000007;
		boolean[] isPrime;
		public void solve(InputReader in, PrintWriter out){ 
			String s = in.next();
			int n = s.length();
			int[][] count = new int[26][n+1];

			for(int i=0; i<s.length(); i++){
				for(int j=0; j<26; j++){
					count[j][i+1] = count[j][i];
				}
				count[s.charAt(i)-'a'][i+1]++;
			}

			int lo=1, hi=n, k=n;
			while(lo<=hi){
				int mid = (lo+hi)>>1;

				boolean valid = false;
				for(int j=0; j<26; j++){
					boolean flag = true;
					for(int i=1; i<=n-mid+1; i++){
						if(count[j][i+mid-1]-count[j][i-1]<=0){
							flag = false;
							break;
						}
					}
					if(flag){
						valid = true;
						break;
					}
				}

				if(valid){
					k = mid;
					hi = mid-1;
				} else {
					lo = mid+1;
				}
			}
			out.println(k);
		}

		void sieve(){
			isPrime = new boolean[MAX];
			Arrays.fill(isPrime, true);
			isPrime[0] = isPrime[1] = false;
			for(int i=2; i<MAX; i++){
				if(isPrime[i]){
					for(int j=i+i; j<MAX; j+=i){
						isPrime[j] = false;
					}
				}
			}
		}

	}
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		public InputReader() {
			reader = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			String s=null;
			try{
				s = reader.readLine();
			} catch(IOException e){
				throw new RuntimeException(e);
			}
			return s;
		}
		public String nextParagraph() {
			String line=null;
			String ans = "";
			try{
				while ((line = reader.readLine()) != null) {
				ans += line;
				}
			} catch(IOException e){
				throw new RuntimeException(e);
			}
			return ans;
		}
	}
}