Leetcode 1647. Minimum Deletions to Make Character Frequencies Unique

Tyan

发布于 2021-08-20 12:13:13

2360

发布于 2021-08-20 12:13:13

文章被收录于专栏：SnailTyan

1. Description

Minimum Deletions to Make Character Frequencies Unique

2. Solution

**解析：**Version 1，先用字典统计每个英文字符出现的频率，然后对频率进行由大到小排序，由大到小排列是因为频率最高的是可以出现的最大次数，使用count表示删除的字符数量，使用pre来表示为了不重复，当前字符删除一部分后的出现次数，初始值为pre = frequencies[0]，比较当前频率与前一个字符频率的大小，如果二者相等，为了不重复，当前频率要减1，即删除一个字符，因此count+=1，同时当前字符的频率减1，如果当前字符频率小于前一个字符的频率，则不需要删除字符，字符频率pre进行更新，如果当前字符频率大于前一个字符的频率，为了不重复，则当前字符要删除frequencies[i] - pre + 1个字符，同时更新pre，如果pre=1，即前一字符的频率已经为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