在Python中计算使字符频率唯一所需的最小删除次数的程序

假设我们有一个字符串s，如果s中没有两个不同的字符具有相同的频率，则s被认为是好的。我们必须找到需要删除的最小字符数，以使s成为“好”的字符串。

因此，如果输入为s =“ssstttuu”，则输出将为2，因为如果我们删除一个“t”，那么将有三个“s”，两个“t”和两个“u”，然后再删除一个，无论是“t”还是“u”，使它们成为好的。

要解决这个问题，我们将遵循以下步骤 −

val：包含s的每个字符的频率的新映射
res：0
numlist：对val中所有频率值的列表进行排序
对于i从0到numlist大小-2，进行以下操作
- 如果numlist [i]是非零的并且与numlist [i + 1]相同，则
  - numlist [i]：= numlist [i] – 1
  - res：= res + 1
  - k：= i-1
  - m：= i
  - while numlist [m]是非零的并且与numlist [k]相同，则
  - numlist [k]：= numlist [k] – 1
  - k：= k-1
  - m：= m-1
  - res：= res + 1
返回res

例子

让我们看看以下实现以更好地理解 –

from collections import Counter
def solve(s):
   val = Counter(s)
   res = 0
   numlist = sorted([i for i in val.values()])
   for i in range(len(numlist)-1):
      if numlist[i] and numlist[i] == numlist[i+1]:
         numlist[i] -= 1
         res += 1
         k = i-1
         m = i
         while numlist[m] and numlist[m] == numlist[k]:
            numlist[k] -= 1
            k -= 1
            m -= 1
            res += 1

   return res

s = "ssstttuu"
print(solve(s))