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.*;
import java.util.function.Consumer;

public class Solution {


    static MyScanner sc;
    private static PrintWriter out;
    static long M2 = 1_000_000_000L + 7;

    public static void main(String[] s) throws Exception {
        StringBuilder stringBuilder = new StringBuilder();

        if (stringBuilder.length() == 0) {
            sc = new MyScanner(System.in);
        } else {
            sc = new MyScanner(new BufferedReader(new StringReader(stringBuilder.toString())));
        }

        out = new PrintWriter(new OutputStreamWriter(System.out));

        initData();
        solve();
        out.flush();
    }

    private static void initData() {

    }


    private static void solve() throws IOException {
        String r = sc.next();
        for (int k = 1; k < r.length(); k++) {
            if (r.charAt(k) != r.charAt(k - 1)) break;
            if (k == r.length() - 1) {
                out.println(1);
                return;
            }
        }

        int m = 1;
        int max = r.length();
        while (m + 1 < max) {
            int mm = (m + max) >>> 1;
            if (v(r, mm)) {
                max = mm;
            } else {
                m = mm;
            }
        }
        out.println(max);
    }

    private static boolean v(String r, int mm) {
        boolean[] dom = new boolean[26];
        Arrays.fill(dom, true);
        int[] ct = new int[26];
        for (int k = 0; k < mm; k++) {
            ct[r.charAt(k) - 'a']++;
        }
        for (int l = 0; l < 26; l++) {
            dom[l] &= ct[l] > 0;
        }
        for (int t = mm; t < r.length(); t++) {
            ct[r.charAt(t) - 'a']++;
            ct[r.charAt(t - mm) - 'a']--;
            for (int l = 0; l < 26; l++) {
                dom[l] &= ct[l] > 0;
            }
        }

        for (boolean rr : dom) {
            if (rr) return true;
        }
        return false;
    }


    private static final class LogTreePar {

        private final int[] levels;
        private final int[][] parents;

        public LogTreePar(int n) {
            levels = new int[n];
            parents = new int[n][19];
            Arrays.fill(levels, -1);
            for (int[] x : parents) {
                Arrays.fill(x, -1);
            }
        }

        public boolean ispar(int f, int l) {
            if (levels[f] >= levels[l]) return false;
            int diff = levels[l] - levels[f];
            return up(l, diff) == f;
        }

        private int up(int item, int diff) {
            int r = 0;
            while (diff > 0 && item >= 0) {
                if (isset(diff, r)) {
                    diff ^= 1 << r;
                    item = parents[item][r];
                }
                r++;
            }
            return item;
        }


        public void add(int item, int parent) {
            parents[item][0] = parent;
            clt(item);
        }


        protected void clt(int item) {
            levels[item] = levels[parents[item][0]] + 1;
            for (int l = 1; l < 19; l++) {
                if (parents[item][l - 1] == -1) break;
                parents[item][l] = parents[parents[item][l - 1]][l - 1];
            }
        }

        public int lca(int f, int l) {
            if (levels[f] > levels[l]) {
                return lca(l, f);
            }
            return lca1(f, up(l, levels[l] - levels[f]));
        }

        private int lca1(int f1, int f2) {
            for (int r = 18; r >= 0 && f1 != f2; r--) {
                if (parents[f1][r] != parents[f2][r]) {
                    f1 = parents[f1][r];
                    f2 = parents[f2][r];
                }
            }
            return f1 == f2 ? f1 : parents[f1][0];
        }
    }


    private static class P {
        private boolean b;
        private final int ind;
        private final int parent;

        public P(int i, boolean b, int par) {
            this.ind = i;
            this.b = b;
            this.parent = par;

        }
    }

    private static void dfs(int start, int[][] neig, Consumer<int[]> onAdd, Consumer<int[]> onRemove) {
        ArrayList<P> toVisit = new ArrayList<P>(3000);
        toVisit.add(new P(start, true, -1));
        boolean[] vis = new boolean[neig.length];
        vis[start] = true;
        int[] level = new int[neig.length];
        while (toVisit.size() > 0) {
            P ppr = toVisit.remove(toVisit.size() - 1);
            if (!ppr.b) {
                onRemove.accept(new int[]{ppr.ind, level[ppr.ind], ppr.parent});
                continue;
            }
            ppr.b = false;
            int i = ppr.ind;
            toVisit.add(ppr);
            onAdd.accept(new int[]{ppr.ind, level[ppr.ind], ppr.parent});
            for (int kk : neig[i]) {
                if (!vis[kk]) {
                    vis[kk] = true;
                    level[kk] = level[i] + 1;
                    toVisit.add(new P(kk, true, i));
                }
            }
        }


    }


    private static int[][] tr(int n) {
        int[][] x = new int[2][n - 1];
        for (int i = 0; i < n - 1; i++) {
            x[0][i] = sc.nextInt() - 1;
            x[1][i] = sc.nextInt() - 1;
        }
        return pn(x, n);
    }

    private static int[][] pn(int[][] x, int n) {
        int[] ct = new int[n];
        int[][] res = new int[n][];
        for (int v : x[0]) {
            ct[v]++;
        }
        for (int v : x[1]) {
            ct[v]++;
        }
        for (int l = 0; l < n; l++) {
            res[l] = new int[ct[l]];
        }
        for (int i = 0; i < x[0].length; i++) {
            res[x[0][i]][--ct[x[0][i]]] = x[1][i];
            res[x[1][i]][--ct[x[1][i]]] = x[0][i];
        }
        return res;
    }


    private static boolean isset(long i, int k) {
        return (i & (1 << k)) > 0;
    }

    private static void solveT() throws IOException {
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }


    private static long gcd(long l, long l1) {
        if (l > l1) return gcd(l1, l);
        if (l == 0) return l1;
        return gcd(l1 % l, l);
    }

    private static long pow(long a, long b, long m) {
        if (b == 0) return 1;
        if (b == 1) return a;
        long pp = pow(a, b / 2, m);
        pp *= pp;
        pp %= m;
        return (pp * (b % 2 == 0 ? 1 : a)) % m;
    }


    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        MyScanner(BufferedReader br) {
            this.br = br;
        }

        public MyScanner(InputStream in) {
            this(new BufferedReader(new InputStreamReader(in)));
        }

        void findToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }

        String next() {
            findToken();
            return st.nextToken();
        }

        Integer[] nab(int n) {
            Integer[] k = new Integer[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        int[] na(int n) {
            int[] k = new int[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        long[] nl(int n) {
            long[] k = new long[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.nextLong();
            }
            return k;
        }

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

        int fi() {
            String t = next();
            int cur = 0;
            boolean n = t.charAt(0) == '-';
            for (int a = n ? 1 : 0; a < t.length(); a++) {
                cur = cur * 10 + t.charAt(a) - '0';
            }
            return n ? -cur : cur;
        }

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

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


}