给出一堆字符,问最少去掉几个字符可以保证每种字符出现的次数不同,用python的counter统计次数,然后用set记录已经出现过的字符频次,若有冲突,不断去掉字符直至不冲突
1 #1647
2 #Runtime: 274 ms (Beats 29.54%)
3 #Memory: 14.2 MB (Beats 87.50%)
4
5 class Solution(object):
6 def minDeletions(self, s):
7 """
8 :type s: str
9 :rtype: int
10 """
11 ans = 0
12 fq_set = set()
13 cnt = collections.Counter(s)
14 for ch, fq in cnt.items():
15 while fq and fq in fq_set:
16 fq -= 1
17 ans += 1
18 fq_set.add(fq)
19 return ans