请教一道MS的OA题目

给定一个只有小写字母的字符串，规定删除一个字符为一次删除操作，求最少删除多少次可以让每个字母出现的频率不一样

先统计频率，然后频率逆序，每一个和前面比较，如果比前面大/等于，则处理为小于1的数，要考虑0带来的影响

1. import collections
   
2. def minDeletions(s):
   
3.     counts = collections.Counter(s)
   
4.     freq = sorted(list(counts.values()),reverse=True)
   
5.     res = 0
   
6.     for i in range(1,len(freq)):
   
7.         if freq[i]>=freq[i-1] and freq[i-1]!=0:
   
8.             res +=freq[i]-freq[i-1]+1
   
9.             freq[i] = freq[i-1]-1
   
10.         elif freq[i-1]==0:
    
11.             res+= freq[i]
    
12.             freq[i]==0
    
13.     return res

复制代码

原理大概就是：
aaabbbcccddd -> aaabbccdd -> aaabbcd -> aaabbc

1. import collections
   
2. 
   
3. 
   
4. class Solution:
   
5.     def mindelete(self, s):
   
6.         result = 0
   
7.         counter = collections.Counter(collections.Counter(s).values())
   
8.         stack = [[key, val] for key, val in counter.items()]
   
9.         # [key, val] = [5, 3] means: There are 3 different characters appear 5 times.
   
10.         stack.sort()
    
11.         while stack:
    
12.             key, val = stack.pop()
    
13.             if key + 1 < val:
    
14.                 return -1       #Impossible cases like "There are 4 chars appear 2 times".
    
15.             result += val - 1
    
16.             if stack and key - 1 == stack[-1][0]:
    
17.                 stack[-1][1] += val - 1
    
18.             elif val - 1 > 0:
    
19.                 stack.append([key - 1, val - 1])
    
20.         return result
    
21. 
    
22. 
    
23. assert(Solution().mindelete('aaabbbcccddd') == 6)
    
24. assert(Solution().mindelete('aabbccdd') == -1)
    
25. assert(Solution().mindelete('aaaabbbccd') == 0)
    
26. assert(Solution().mindelete('aaaab') == 0)
    
27. assert(Solution().mindelete('aaaaaaaaaabbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffff') == 15)
    

复制代码

我感觉是bucket sort类似的问题，先把数组每个字符频率统计出来，然后从最高的频率往下处理。如果有重复频率就删的只剩一个，以此类推

25！ ？

先统计 字母:频率
然后把 频率：字母数 加入到一个treemap
从大到小过一遍频率
如果当前频率的个数m大于1，那么修改就要增加 m-1,同时udpate map, 当前频率-1：m-1