読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

Codeforces Round #352 (Div. 2) B. Different is Good

codeforces

問題
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;
}