CodeChef K-good Words

問題

https://www.codechef.com/problems/KGOOD

文字列 s が与えられる。s 内に現れる文字 c0, c1 について, |(c0 が s 内で現れる回数)-(c1 が s 内で現れる回数)| <= K を満たすとき, s を K-good Word と呼ぶ。s 内の文字を好きに消して, s を K-good Word にしたい。最小の消す回数を求めよ。

解法

最小回数現れる文字 c を決めうちします。すると,

• s 内で c より現れる回数が少ない文字は 出現回数を 0 にするしかない
• そうでない文字は出現回数を (c の出現回数)+K 以内に抑える

とすれば良さそうです。

int cnt[26];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        string s;
        int K;
        cin >> s >> K;
        memset(cnt, 0, sizeof(cnt));
        for (char c : s) {
            cnt[c-'a']++;
        }
        sort(cnt, cnt+26);
        int ans = s.size();
        for (int i = 0; i < 26; i++) {
            if (!cnt[i]) continue;
            int tmp = 0;
            for (int j = 0; j < i; j++) 
                tmp += cnt[j];
            for (int j = i+1; j < 26; j++) {
                if (cnt[j]-cnt[i] > K) tmp += cnt[j]-cnt[i]-K;
            }
            ans = min(ans, tmp);
        }
        cout << ans << endl;
    }
    return 0;
}