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
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T BM(T p, T e, T M) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T mdINV(T a, T M) {
  return BM(a, M - 2, M);
}
template <class T>
inline T PW(T p, T e) {
  long long int ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p);
    p = (p * p);
  }
  return (T)ret;
}
template <class T>
bool ISLEFT(T a, T b, T c) {
  if (((a.first.first - b.first.first) * (b.second.second - c.second.second) -
       (b.first.first - c.first.first) * (a.second.second - b.second.second)) <
      0.0)
    return 1;
  else
    return 0;
}
char a[200004 + 2];
int ar[27][200004 + 2];
int main() {
  scanf("%s", a + 1);
  int l = strlen(a + 1);
  for (int i = 1; i <= 26; i++) {
    for (int j = 1; j <= l; j++) {
      ar[i][j] = ar[i][j - 1];
      if (a[j] - 'a' + 1 == i) ar[i][j]++;
    }
  }
  int lo = 0, hi = 200004 + 2;
  int ans = l;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    bool f = 0;
    for (int j = 1; j <= 26; j++) {
      bool fl = 0;
      for (int k = 1; k <= l - mid + 1; k++) {
        if (ar[j][k + mid - 1] - ar[j][k - 1] == 0) fl = 1;
      }
      if (fl == 0) {
        f = 1;
        break;
      }
    }
    if (f) {
      hi = mid - 1;
      ans = mid;
    } else
      lo = mid + 1;
  }
  printf("%d", ans), printf("\n");
  return 0;
}
