1647. Minimum Deletions to Make Character Frequencies Unique

O(n) time O(26) space

class Solution {
public:
    int minDeletions(string s) {
        int f[26] = {0};
        for (char c : s) {
            ++f[c - 'a'];
        }
        sort(f, f + 26, greater());
        int res = 0;
        for (int i = 1; i < 26 && f[i]; ++i) {
            if (f[i] >= f[i - 1]) { // 有可能出现多个频数一样的减完会比下一个频数小，比如"abcabc"
                int x = max(0, f[i - 1] - 1); // 有可能前一个频数已为0
                res += f[i] - x;
                f[i] = x;
            }
        }
        return res;
    }
};