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






/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */


import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;


/**
 *
 * @author jmbangue
 */
public class KDominantCharacter {

    public static void main(String[] args){
        BufferedInputStream bf = new BufferedInputStream(System.in);
        BufferedReader r = new BufferedReader(
                new InputStreamReader(bf, StandardCharsets.UTF_8));
        OutputStream out = new BufferedOutputStream ( System.out );
        try {
            
            String s = r.readLine();
            char[] ca = s.toCharArray();
            HashMap<Character,List<Integer>> map = new HashMap<>();
            int n = s.length();
            for(int i=0;i<n;i++){
                if (map.get(ca[i])==null) map.put(ca[i], new ArrayList<Integer>());
                map.get(ca[i]).add(i);
            }
            int md = 0;
            for(char key:map.keySet()){
                int  st = -1, step = 0;
                List<Integer> a  = map.get(key);
                for(int j:a){
                    step = Math.max(step,j - st);
                    st = j;
                }
                if (st<n-1) step = Math.max(step, n - st);
                md = md == 0 ? (step ) : Math.min(md,(step));
            }

            out.write((md+"\n").getBytes());
            out.flush();
        }catch(Exception ex){
            ex.printStackTrace();
        }
        
         
    }
    
    private static int readInt(InputStream in) throws IOException {
            int ret = 0;
            boolean dig = false;

            for (int c = 0; (c = in.read()) != -1; ) {
                if (c >= '0' && c <= '9') {
                    dig = true;
                    ret = ret * 10 + c - '0';
                } else if (dig) break;
            }

            return ret;
    }
}
