Codeforces Round #352 (Div. 2) B. Different is Good
問題
Problem - B - Codeforces
文字列が与えられる.どの部分列をとっても同じ文字列が現れないように与えられた文字列を書き換えるとき,書き換える最小の文字数は幾つか.
解法
部分列は1文字だけ考えればよい.つまり,すべて違う文字になるように書き換えるときの最小の値を求める.文字列が26文字以上の時はそのような文字列は存在しないので-1を返す.
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define RREP(i,s,e) for (i = s; i >= e; i--) #define rrep(i,n) RREP(i,(int)(n)-1,0) #define REP(i,s,e) for (i = s; i <= e; i++) #define rep(i,n) REP(i,0,(int)(n)-1) #define INF 100000000 typedef long long ll; int main() { int i, n, ans; int cnt[26] {}; string s; cin >> n; if (n > 26) { cout << -1 << endl; return 0; } cin >> s; for (auto c : s) cnt[c-'a']++; ans = 0; rep (i,26) { if (cnt[i] > 1) ans += cnt[i]-1; } cout << ans << endl; return 0; }