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>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &item : v) is >> item;
  return is;
}
template <class T1, class T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}
template <template <typename, typename...> class V, typename... Args>
typename std::enable_if<!std::is_same<std::string, V<Args...>>::value,
                        ostream &>::type
operator<<(ostream &os, const V<Args...> &cont) {
  for (const auto &item : cont) os << item << " ";
  os << endl;
  return os;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << p.first << ';' << p.second;
  return os;
}
template <class T>
struct VectorHasher {
  T operator()(const vector<T> &V) const {
    T hash = 0;
    for (size_t i = 0; i < V.size(); i++) hash ^= V[i];
    return hash;
  }
};
static int _ = [] {
  ios_base::sync_with_stdio(false);
  return 0;
}();
int main() {
  string s;
  while (cin >> s) {
    unordered_map<char, vector<int>> um;
    for (int i = 0; i < s.size(); i++) um[s[i]].push_back(i);
    int res = s.size();
    for (auto &p : um) {
      auto &inds = p.second;
      inds.push_back(s.size());
      int max_d = 0;
      for (int i = 1; i < inds.size(); i++)
        max_d = max(max_d, inds[i] - inds[i - 1]);
      max_d = max<int>(max_d, *inds.begin() - (-1));
      res = min(res, max_d);
    }
    cout << res << endl;
    break;
    cout << "------------------------\n";
  }
  return 0;
}
