文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書

1. Description

Minimum Deletions to Make Character Frequencies Unique

2. Solution

解析：Version 1，先用字典統(tǒng)計(jì)每個(gè)英文字符出現(xiàn)的頻率，然后對頻率進(jìn)行由大到小排序，由大到小排列是因?yàn)轭l率最高的是可以出現(xiàn)的最大次數(shù)，使用count表示刪除的字符數(shù)量，使用pre來表示為了不重復(fù)，當(dāng)前字符刪除一部分后的出現(xiàn)次數(shù)，初始值為pre = frequencies[0]，比較當(dāng)前頻率與前一個(gè)字符頻率的大小，如果二者相等，為了不重復(fù)，當(dāng)前頻率要減1，即刪除一個(gè)字符，因此count+=1，同時(shí)當(dāng)前字符的頻率減1，如果當(dāng)前字符頻率小于前一個(gè)字符的頻率，則不需要?jiǎng)h除字符，字符頻率pre進(jìn)行更新，如果當(dāng)前字符頻率大于前一個(gè)字符的頻率，為了不重復(fù)，則當(dāng)前字符要?jiǎng)h除frequencies[i] - pre + 1個(gè)字符，同時(shí)更新pre，如果pre=1，即前一字符的頻率已經(jīng)為1，則后面的字符要全刪除，相等和大于的情況可以合并到一起。

• Version 1

class Solution:
    def minDeletions(self, s: str) -> int:
        stat = collections.defaultdict(int)
        for ch in s:
            stat[ch] += 1
        frequencies = sorted(stat.values(), reverse=True)
        count = 0
        pre = frequencies[0]
        for i in range(1, len(frequencies)):
            if pre == 1:
                count += frequencies[i]
                continue
            if frequencies[i] >= pre:
                count += frequencies[i] - pre + 1
                pre -= 1
            else:
                pre = frequencies[i]
        return count

Reference

1. https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/