AGC016: A - Shrinking

問題

A - Shrinking

解説

最終的に残る文字種を全探索し、題意に沿うようにシミュレーションする。 「 i, i+1 文字目のどちらかである」について、決め打ちした文字と一致しているものがあればをそちらを優先して選べば良い。

探索に使っている文字が入力の文字列に含まれないこともあるが、特にそういったケースは気にせずにすべての文字種について同じ処理をして問題ない。

template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }

bool is_uniq(string t) {
  t.erase(std::unique(t.begin(), t.end()), t.end());
  return t.size() == 1;
}

int solve(string s, char ch) {
  rep(i, inf) {
    string t;
    rep(j, s.size() - 1) {
      if (s[j] == ch) {
        t.push_back(s[j]);
      } else {
        t.push_back(s[j + 1]);
      }
    }
    if (is_uniq(t)) {
      return i + 1;
    }
    s = t;
  }
  assert(false);
}

int main() {
  string s; cin >> s;
  if (is_uniq(s)) { cout << "0\n"; exit(0); }
  int ans = inf;
  rep(chi, 26) {
    auto ch = char('a' + chi);
    minimize(ans, solve(s, ch));
  }
  cout << ans << endl;
}