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.math.BigInteger;
import java.util.*;

public class main
{
	private static InputStream stream;
	private static byte[] buf = new byte[1024];
	private static int curChar;
	private static int numChars;
	private static SpaceCharFilter filter;
	private static PrintWriter pw;
	private static long mod = 1000000000 + 7;
	private static TreeSet<Integer> set;
	// H " " J G ' '
	private static void soln()
	{
		String s = nextLine();
		int l = 1;
		int r = s.length();
		int n = r;
		int ans =Integer.MAX_VALUE;
		while(l<=r) {
			int mid = (l+r)/2;
			boolean f = false;
			for(int j=0;j<26;j++) {
				int prev = -1;
				boolean f1 = true;
				for(int i=0;i<n;i++) {
					if((s.charAt(i)-'a')==j) {
						 if(i-prev > mid) {
							f1 = false;
							break;
						}else
							prev = i;
					}
				}
				if(n-prev-1 >= mid)
					f1 = false;
				if(f1) {
					f=true;
					break;
				}
			}
			if(f) {
				r=mid-1;
				ans = mid;
			}else
				l=mid+1;
			
		}
		pw.println(ans);
	}
	private static class DSU
	{
		int[] parent;
		int[] rank;
		int cnt;

		public DSU(int n)
		{
			parent = new int[n];
			rank = new int[n];
			for (int i = 0; i < n; i++)
			{
				parent[i] = i;
			}
			cnt = n;
		}

		int find(int i)
		{
			while (parent[i] != i)
			{
				parent[i] = parent[parent[i]];
				i = parent[i];
			}
			return i;
		}

		void Union(int x, int y)
		{
			int x1 = find(x);
			int y1 = find(y);
			if (rank[x1] < rank[y1])
			{
				parent[x1] = y1;
			} else if (rank[x1] > rank[y1])
			{
				parent[y1] = x1;
			} else
			{
				parent[x1] = y1;
				rank[y1]++;
			}
		}
	}

	public static class Segment
	{
		private Node[] tree;
		private boolean[] lazy;
		private int size;
		private int n;

		private class Node
		{
			private int l;
			private int r;
			private long ans;
			
		}

		public Segment(int n)
		{
			// this.base=arr;
			int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
			size = 2 * (int) Math.pow(2, x) - 1;
			tree = new Node[size];
			lazy = new boolean[size];
			this.n = n;
			//build(0, 0, n - 1);
		}

		public void build(int id, int l, int r)
		{
			if (l == r)
			{
				if(set.contains(l)) {
					tree[id] = new Node();
					tree[id].l = l;
					tree[id].r = r;
				}
				return;
			}
			int mid = (l + r) / 2;
			build(2 * id + 1, l, mid);
			build(2 * id + 2, mid + 1, r);
			tree[id] = merge(tree[2*id+1], tree[2*id+2]);
			System.out.println(l+" "+r+" "+tree[id].l+" "+tree[id].r+" "+tree[id].ans);
		}
		public Node merge(Node n1, Node n2) {
			if(n1 == null)
				return n2;
			if(n2 == null)
				return n1;
			Node ret = new Node();
			ret.l = n1.l;
			ret.r = n2.r;
			ret.ans = n1.ans + n2.ans;
			long diff = n2.l - n1.r - 1;
			ret.ans += (diff*(diff+1))/2;
			
			return ret;
		}
		public long query(int l, int r)
		{
			Node ret = queryUtil(l, r, 0, 0, n - 1);
			if(ret == null)
				return 0;
			else
				return ret.ans;
		}

		private Node queryUtil(int x, int y, int id, int l, int r)
		{
			if (l > y || x > r)
				return null;
			if (x <= l && r <= y)
			{
				return tree[id];
			}
			int mid = l + (r - l) / 2;
			// shift(id);
			Node q1 = queryUtil(x, y, 2 * id + 1, l, mid);
			Node q2 = queryUtil(x, y, 2 * id + 2, mid + 1, r);
			return merge(q1, q2);
		}
		
		public void update(int x, int y, int c) {
			update1(x, y, c, 0, 0, n-1);
		}
		
		private void update1(int x, int y, int colour, int id, int l, int r)
		{
			// System.out.println(l+" "+r+" "+x);
			if (x > r || y < l)
				return;
			if (x <= l && r <= y)
			{
				if(set.contains(x)) {
					tree[id] = new Node();
					tree[id].l = l;
					tree[id].r = r;
					tree[id].ans = 0;
				}else
					tree[id] = null;
			}
			int mid = l + (r - l) / 2;
			// shift(id);
			update1(x, y, colour, 2 * id + 1, l, mid);
			update1(x, y, colour, 2 * id + 2, mid + 1, r);
			tree[id] = merge(tree[2*id+1], tree[2*id+2]);
		}

		public void shift(int id)
		{

		}
	}

	public static void fft(double[] a, double[] b, boolean invert)
	{
		int count = a.length;
		for (int i = 1, j = 0; i < count; i++)
		{
			int bit = count >> 1;
			for (; j >= bit; bit >>= 1)
				j -= bit;
			j += bit;
			if (i < j)
			{
				double temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				temp = b[i];
				b[i] = b[j];
				b[j] = temp;
			}
		}
		for (int len = 2; len <= count; len <<= 1)
		{
			int halfLen = len >> 1;
			double angle = 2 * Math.PI / len;
			if (invert)
				angle = -angle;
			double wLenA = Math.cos(angle), wLenB = Math.sin(angle);
			for (int i = 0; i < count; i += len)
			{
				double wA = 1, wB = 0;
				for (int j = 0; j < halfLen; j++)
				{
					double uA = a[i + j], uB = b[i + j];
					double vA = a[i + j + halfLen] * wA - b[i + j + halfLen] * wB;
					double vB = a[i + j + halfLen] * wB + b[i + j + halfLen] * wA;
					a[i + j] = uA + vA;
					b[i + j] = uB + vB;
					a[i + j + halfLen] = uA - vA;
					b[i + j + halfLen] = uB - vB;
					double nextWA = wA * wLenA - wB * wLenB;
					wB = wA * wLenB + wB * wLenA;
					wA = nextWA;
				}
			}
		}
		if (invert)
		{
			for (int i = 0; i < count; i++)
			{
				a[i] /= count;
				b[i] /= count;
			}
		}
	}

	static void multiply(long[][] a, long[][] b, long m)
	{
		int n = a.length;
		long[][] mul = new long[n][n];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				mul[i][j] = 0;
				for (int k = 0; k < n; k++)
					mul[i][j] = (mul[i][j] + (a[i][k] * b[k][j]) % m) % m;
			}
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				a[i][j] = mul[i][j];
	}

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

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

	public static void main(String[] args) throws Exception
	{
		new Thread(null, new Runnable()
		{
			@Override
			public void run()
			{
				/*
				 * try { InputReader(new
				 * FileInputStream("C:\\Users\\hardik\\Desktop\\B-large-practice.in")); } catch
				 * (FileNotFoundException e) { // TODO Auto-generated catch block
				 * e.printStackTrace(); }
				 */
				InputReader(System.in);
				pw = new PrintWriter(System.out);
				/*
				 * try { pw=new PrintWriter(new
				 * FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt")); } catch
				 * (FileNotFoundException e) { // TODO Auto-generated catch block
				 * e.printStackTrace(); }
				 */
				soln();
				pw.close();
			}
		}, "1", 1 << 26).start();

		/*
		 * try { InputReader(new
		 * FileInputStream("C:\\Users\\hardik\\Desktop\\B-large-practice.in")); } catch
		 * (FileNotFoundException e) { // TODO Auto-generated catch block
		 * e.printStackTrace(); }
		 */
		// InputReader(System.in);
		// pw = new PrintWriter(System.out);
		/*
		 * try { pw=new PrintWriter(new
		 * FileOutputStream("C:\\Users\\hardik\\Desktop\\out.txt")); } catch
		 * (FileNotFoundException e) { // TODO Auto-generated catch block
		 * e.printStackTrace(); }
		 */
		// soln();
		// pw.close();
	}

	public static void InputReader(InputStream stream1)
	{
		stream = stream1;
	}

	private static boolean isWhitespace(int c)
	{
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private static boolean isEndOfLine(int c)
	{
		return c == '\n' || c == '\r' || c == -1;
	}

	private static int read()
	{
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars)
		{
			curChar = 0;
			try
			{
				numChars = stream.read(buf);
			} catch (IOException e)
			{
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	private static int nextInt()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-')
		{
			sgn = -1;
			c = read();
		}
		int res = 0;
		do
		{
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static long nextLong()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-')
		{
			sgn = -1;
			c = read();
		}
		long res = 0;
		do
		{
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	private static String nextToken()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do
		{
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private static String nextLine()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do
		{
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	private static int[] nextIntArray(int n)
	{
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
		{
			arr[i] = nextInt();
		}
		return arr;
	}

	private static long[] nextLongArray(int n)
	{
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
		{
			arr[i] = nextLong();
		}
		return arr;
	}

	private static void pArray(int[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static void pArray(long[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		return;
	}

	private static boolean isSpaceChar(int c)
	{
		if (filter != null)
			return filter.isSpaceChar(c);
		return isWhitespace(c);
	}

	private static char nextChar()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		char c1 = (char) c;
		while (!isSpaceChar(c))
			c = read();
		return c1;
	}

	private interface SpaceCharFilter
	{
		public boolean isSpaceChar(int ch);
	}
}