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.*;

/**
 * Created by Artem on 15.09.2017.
 */
public class Task {
    private String NAME = "";
    private String ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE");
    private BufferedReader in;
    private PrintWriter out;
    private StringTokenizer tok;

    public void init() throws FileNotFoundException {
        if (ONLINE_JUDGE != null) {
            if (NAME == "") {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(NAME + ".in"));
                out = new PrintWriter(NAME + ".out");
            }
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
        tok = new StringTokenizer("");
    }

    private String readLine() throws IOException {
        return in.readLine();
    }

    private String readString() throws IOException {
        if (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    public int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    public long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    public double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    public int[] readIntArray(int n) throws IOException {
        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            array[i] = readInt();
        }
        return array;
    }

    private long timeBegin, timeEnd;

    public static void main(String[] args) throws IOException {
        new Task().run();
    }

    class Pair<X, Y> implements Comparable<Pair<X, Y>> {
        X x;
        Y y;

        public Pair(X x, Y y) {
            this.x = x;
            this.y = y;
        }

        X getX() {
            return x;
        }

        Y getY() {
            return y;
        }

        @Override
        public int compareTo(Pair<X, Y> o) {
            if (x instanceof Comparable && y instanceof Comparable) {
                int result = ((Comparable) x).compareTo(o.x);
                if (result == 0) {
                    return ((Comparable) y).compareTo(o.y);
                } else {
                    return -result;
                }
            }
            return 0;
        }

    }

    public void run() throws IOException {
        timeBegin = System.currentTimeMillis();
        init();
        solve();
        if (ONLINE_JUDGE == null) {
            //time();
        }

        out.close();
    }

    public void time() {
        timeEnd = System.currentTimeMillis();
        out.println();
        out.println("Time =" + (timeEnd - timeBegin));
    }

    //YOUR SOLVE////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    public void solve() throws IOException {
        String in = readLine();
        int[] min = new int[26];
        int[] last = new int[26];
        Arrays.fill(last, -1);

        for (int i = 0; i < in.length(); i++) {
            int index = in.charAt(i) - 'a';
            min[index] = Math.max(i - last[index], min[index]);
            last[index] = i;
        }
        for (int i = 0; i < 26; i++) {
            min[i] = Math.max(min[i], in.length() - last[i]);
        }

        int minimum = 100001;
        for (int i = 0; i < 26; i++) {
            if (min[i] != 0) {
                minimum = Math.min(min[i], minimum);
            }
        }
        out.print(minimum);

    }

}