字符频次唯一的最小删除次数

如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。
给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。
字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 “aab” 中，’a’ 的频次是 2，而 ‘b’ 的频次是 1 。

  • 输入：s = “aab”

  • 输出：0

  • 解释：s 已经是优质字符串。

  • 输入：s = “aaabbbcc”

  • 输出：2

  • 解释：可以删除两个 ‘b’ , 得到优质字符串 “aaabcc” 。
    另一种方式是删除一个 ‘b’ 和一个 ‘c’ ，得到优质字符串 “aaabbc” 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var minDeletions = function(s) {
    const cnt = Object.values(_.countBy(s)).sort((a, b) => b - a)
    let ans = 0
    for (let i = 1; i < cnt.length; i ++) {
        if (cnt[i] >= cnt[i - 1] && cnt[i - 1] >= 1) {
            ans += (cnt[i] - cnt[i - 1]) + 1
            cnt[i] = cnt[i - 1] - 1
        }
        if (cnt[i - 1] === 0) {
            ans += cnt[i]
            cnt[i] = 0
        }
    }
    return ans
};