3545. Minimum Deletions for At Most K Distinct Characters

You are given a string s consisting of lowercase English letters, and an integer k.

Your task is to delete some (possibly none) of the characters in the string so that the number of distinct characters in the resulting string is at most k.

Return the minimum number of deletions required to achieve this.

class Solution {
public:
    int minDeletion(string s, int k) {
        unordered_map<char,int> freq;
        for(auto& ch : s) freq[ch]++;
        vector<int> S;
        for(auto& [_,v] : freq) S.push_back(v);
        int res = 0;
        sort(rbegin(S), rend(S));
        while(S.size() > k) {
            res += S.back(); S.pop_back();
        }
        return res;
    }
};