Leetcode 1647. Minimum Deletions to Make Character Frequencies Unique

布满荆棘的人生 2022-09-05 14:51 42阅读 0赞

文章作者：Tyan  
博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1]

## 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

## Reference ##

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

[noahsnail.com]: http://noahsnail.com
[CSDN]: http://blog.csdn.net/quincuntial
[Link 1]: http://www.jianshu.com/users/7731e83f3a4e/latest_articles
[Minimum Deletions to Make Character Frequencies Unique]: /images/20220829/98b6fed73ea446abb73db241bfdde612.png
[https_leetcode.com_problems_minimum-deletions-to-make-character-frequencies-unique]: https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/