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 <typename T>
void incontainer(std::vector<T> &v) {
  for (size_t i = 0; i < v.size(); i++) {
    std::cin >> v[i];
    ;
  }
}
template <typename T>
void outcontainer(std::vector<T> &v) {
  for (size_t i = 0; i < v.size(); i++) {
    std::cout << v[i] << " "
              << "";
    ;
  }
  std::cout << std::endl;
  ;
}
template <typename T>
void inmatrix(std::vector<std::vector<T> > &v) {
  for (size_t i = 0; i < v.size(); i++) {
    for (size_t j = 0; j < v[i].size(); j++) {
      std::cin >> v[i][j];
    }
  }
}
std::vector<std::string> split(char c, std::string s) {
  std::vector<std::string> v;
  std::string temp = "";
  for (int i = 0; i < (int)s.size(); i++) {
    if (s[i] == c) {
      if (temp != "") {
        v.push_back(temp);
        temp = "";
      }
    } else {
      temp = temp + s[i];
    }
  }
  if (temp != "") {
    v.push_back(temp);
  }
  return v;
}
template <typename T>
inline bool isodd(T x) {
  return ((x % 2) == 1);
}
inline bool findchar(char c, std::string s) {
  return (s.find(c) != std::string::npos);
}
inline int stringdiff(const std::string &a, const std::string &b) {
  int cnt = 0;
  for (int i = 0; i < (int)min(a.size(), b.size()); i++) {
    if (a[i] != b[i]) {
      cnt++;
    }
  }
  return cnt;
}
int main() {
  int t = 1;
  while (t-- > 0) {
    std::string s;
    std::cin >> s;
    ;
    int n = s.size();
    std::vector<int> a(26, 0);
    std::vector<int> b(26, -1);
    for (int i = 0; i < (int)n; i++) {
      int c = s[i] - 'a';
      a[c] = max(a[c], i - b[c]);
      b[c] = i;
    }
    for (int i = 0; i < (int)26; i++) {
      a[i] = max(a[i], min(n - b[i], n));
    }
    int minv = a[0];
    for (int i = 0; i < (int)26; i++) {
      minv = min(minv, a[i]);
    }
    std::cout << minv << std::endl;
    ;
  }
}
