Python程序：查找形成包含K个唯一字符的字符串所需的最少更改次数

假设我们有一个包含小写字母字符的字符串s，还有一个数字k，我们必须找到对字符串进行的最少更改次数，以便生成的字符串最多包含k个不同的字符。在这种情况下，更改实际上是将单个字符更改为任何其他字符。

因此，如果输入类似于s = "wxxyyzzxx"，k = 3，则输出将为1，因为我们可以删除字母“w”以获得3个不同的字符（x、y和z）。

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

• count := s中每个字符及其频率的映射

• sv := 排序后的频率值列表

• ans := 0

• 对于范围从0到(count的大小) - k - 1的i，执行：

  • ans := ans + sv[i]

• 返回ans

让我们来看下面的实现，以便更好地理解：

示例

在线演示

from collections import Counter
class Solution:
   def solve(self, s, k):
      count = Counter(s)
      sv = sorted(count.values())
      ans = 0
      for i in range(len(count) - k):
         ans += sv[i]
      return ans

ob = Solution()
s = "wxxyyzzxx"
k = 3
print(ob.solve(s, k))

输入

"wxxyyzzxx",3

输出

1

Arnab Chakraborty

更新于：2020年10月9日

407 次浏览

开启你的职业生涯

完成课程获得认证

开始学习