用 Python 编写一个程序，计算使字符频率唯一所需的最少删除次数

pythonserver side programmingprogramming更新于 2025/11/30 5:00:17

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

因此，如果输入为 s = "ssstttuu"，则输出将为 2，因为如果我们删除一个 't'，那么将有三个 's'、两个 't' 和两个 'u'，然后再次删除一个，要么是 't'或 'u'，使它们变好。

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

val := 一个包含 s 中每个字符频率的新映射
res := 0
numlist := 从 val 对所有频率值列表进行排序
对于范围从 0 到 numlist 大小 -2 的 i，执行
- 如果 numlist[i] 非零且 numlist[i] 与 numlist[i+1] 相同，则
  - numlist[i] := numlist[i] - 1
  - res := res + 1
  - k := i-1
  - m := i
  - 而numlist[m] 非零且 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))