LeetCode 1647. [Python] Minimum Deletions to Make Character Frequencies Unique
原题链接
中等
作者:
徐辰潇
,
2021-08-17 06:50:44
,
所有人可见
,
阅读 573
class Solution:
def minDeletions(self, s: str) -> int:
#TC: O(len(s))
#SC: O(max(freq(len(s))))
#Just decrease characters with repetiting frequency to a frequency that is never seen
freq = {}
for c in s:
freq[c] = 1 + freq.get(c,0)
seen = set([])
res = 0
for i in freq.values():
if i not in seen:
seen.add(i)
else:
while i > 0 and i in seen:
i -= 1
res += 1
if i > 0:
seen.add(i)
return res