2025-10-28：不同字符数量最多为 K 时的最少删除数。用go语言，给定一个只含小写字母的字符串 s 和一个整数 k。

你可以从 s 中去除若干字符（也可以不动任何字符），目标是让剩下的字符串中不同字母的种类不超过 k。

请计算并返回为了达到这一目标，最少需要删除多少个字符。

1 <= s.length <= 16。

1 <= k <= 16。

s 仅由小写英文字母组成。

输入： s = “abc”, k = 2。

输出： 1。

解释：

s 有三个不同的字符：‘a’、‘b’ 和 ‘c’，每个字符的出现频率为 1。

由于最多只能有 k = 2 个不同字符，需要删除某一个字符的所有出现。

例如，删除所有 ‘c’ 后，结果字符串中的不同字符数最多为 k。因此，答案是 1。

题目来自力扣3545。

解题步骤分析

1. 统计字符频率

首先，代码创建了一个长度为26的整数数组 cnt，用于统计字符串 s 中每个小写字母出现的次数。通过遍历字符串，对每个字符 b，计算 b - 'a' 得到其对应的索引（0对应’a’，1对应’b’，…，25对应’z’），然后将该索引在 cnt 数组中的值加1。例如，对于输入字符串 s = "abc"，数组 cnt 中索引为0（‘a’）、1（‘b’）和2（‘c’）的位置值均为1，其余23个位置为0。

2. 对频率数组进行排序

接下来，使用 slices.Sort 函数对 cnt 数组进行升序排序。排序后，出现次数最少的字符频率会排在数组的前面，而出现次数最多的字符频率会排在后面。对于示例 s = "abc"，排序后的 cnt 数组前23个位置为0，最后三个位置为1（顺序不定，但值都是1）。

3. 计算最少删除数量

排序完成后，代码开始计算最少需要删除的字符数。变量 ans 初始化为0，用于累计删除的数量。

• 核心逻辑是：为了将不同字母的种类数减少到不超过 k，我们倾向于保留出现频率最高的 k 种字符，因为保留高频字符意味着需要删除的字符总数更少。
• 代码通过循环 for _, c := range cnt[:26-k] 实现这一策略。这个循环遍历的是排序后频率数组中的前 26 - k 个元素（即出现频率最低的那些字符）。对于这些字符，选择将它们全部删除，并将它们的出现次数 c 累加到结果 ans 中。
• 为什么是前 26 - k 个？因为我们的目标是只保留最多 k 种字符。在排序后的数组中，后 k 个位置对应着出现频率最高的 k 种字符，这些是我们决定保留的。那么，剩下的 26 - k 种字符（即频率最低的那些）就是我们需要考虑删除的。

以你的例子 s = "abc", k = 2 来说明：

• 字符串有3种不同字符，但 k=2，所以需要减少1种字符。
• 排序后的频率数组后 k=2 位是两种出现频率为1的字符（被保留），前 26-2=24 位中包含一种出现频率为1的字符（被删除）。
• 因此，需要删除的字符数就是这种被删除字符的频率，即1。

复杂度分析

总的时间复杂度

• 统计字符频率：需要遍历整个字符串 s，其长度为 n。因此，这一步的时间复杂度为 O(n)。
• 排序频率数组：频率数组 cnt 的长度固定为26。对固定长度的数组进行排序，时间复杂度可以看作是 O(1)，因为26是一个常数。常用的排序算法（如快速排序）对26个元素排序的时间是常数时间。
• 计算删除数量：循环遍历频率数组中的前 26 - k 个元素，由于数组大小固定为26，这个循环的迭代次数不会超过26，因此时间复杂度也是 O(1)。

综上，总的时间复杂度主要由遍历字符串决定，为 O(n)。

总的额外空间复杂度

• 代码使用了一个固定大小为26的整数数组 cnt 来存储字符频率。除此之外，排序操作（slices.Sort）可能会使用一些栈空间（对于快速排序），但由于输入数组大小固定为26，这个栈空间深度也是常数级别的。
• 没有使用其他与输入规模 n 相关的额外空间。

因此，总的额外空间复杂度为 O(1)。

这个解法巧妙地利用了固定大小的频率数组，使得算法非常高效，特别适合题目中给出的字符串长度限制（1 <= s.length <= 16）。

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

func minDeletion(s string, k int) (ans int) {
	cnt := [26]int{}
	for _, b := range s {
		cnt[b-'a']++
	}

	slices.Sort(cnt[:])
	for _, c := range cnt[:26-k] {
		ans += c
	}
	return
}

func main() {
	s := "abc"
	k := 2
	result := minDeletion(s, k)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def minDeletion(s: str, k: int) -> int:
    # 统计每个字符的出现次数
    cnt = [0] * 26
    for char in s:
        cnt[ord(char) - ord('a')] += 1
    
    # 对出现次数进行排序（从小到大）
    cnt.sort()
    
    # 保留出现次数最多的k个字符，删除其他所有字符
    # 由于是升序排序，最后k个是最大的
    ans = 0
    for i in range(26 - k):
        ans += cnt[i]
    
    return ans

# 测试
s = "abc"
k = 2
result = minDeletion(s, k)
print(result)