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
/**
 * ******* Created  on 8/4/20 4:52 AM*******
 */

import java.io.*;
import java.util.*;

public class C888 implements Runnable {

    private static final int MAX = (int) (1E5 + 5);
    private static final int oo = (int) (1E7 + 10);

    private void solve() throws IOException {
        int[][] last = new int[MAX][26];
        int[][] prev = new int[MAX][26];
        String s = reader.next();
        int n = s.length();
        for(int j =0;j<26;j++)
            last[n][j] = n;
        for(int i=n-1;i>=0;i--){
            for(int j =0;j<26;j++){
                last[i][j] = last[i+1][j];
            }
            last[i][s.charAt(i)-'a'] = i;
        }
        for(int j=0;j<26;j++)
            prev[0][j] = -1;
        prev[0][s.charAt(0)-'a']=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<26;j++)
                prev[i][j] = prev[i-1][j];
            prev[i][s.charAt(i)-'a']=i;
        }
        int ans = n;
        for(int j=0;j<26;j++){
            int val = 0;
            for(int i=0;i<n;i++){
                    if(s.charAt(i)-'a' == j)
                        val = Math.max(val,1);
                    else
                        val = Math.max(val,Math.max(last[i][j]- i+1, i- prev[i][j]+1 ));

            }

            val = Math.max(last[0][j]+1,val);
            val = Math.max(val, n-prev[n-1][j]);

            ans =Math.min(ans, val);
        }
        writer.println(ans);
    }

    public static void main(String[] args) throws IOException {
        try (Input reader = new StandardInput(); PrintWriter writer = new PrintWriter(System.out)) {
            new C888().run();
        }
    }

    StandardInput reader;
    PrintWriter writer;

    @Override
    public void run() {
        try {
            reader = new StandardInput();
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    interface Input extends Closeable {
        String next() throws IOException;

        default int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

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

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

        default int[] readIntArray() throws IOException {
            return readIntArray(nextInt());
        }

        default int[] readIntArray(int size) throws IOException {
            int[] array = new int[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        default long[] readLongArray(int size) throws IOException {
            long[] array = new long[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextLong();
            }
            return array;
        }
    }

    private static class StandardInput implements Input {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        private StringTokenizer stringTokenizer;

        @Override
        public void close() throws IOException {
            reader.close();
        }

        @Override
        public String next() throws IOException {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(reader.readLine());
            }
            return stringTokenizer.nextToken();
        }
    }
}

