LeetCode 题解工作台
不同字符数量最多为 K 时的最少删除数
给你一个字符串 s （由小写英文字母组成）和一个整数 k 。 你的任务是删除字符串中的一些字符（可以不删除任何字符），使得结果字符串中的 不同字符数量 最多为 k 。 返回为达到上述目标所需删除的 最小 字符数量。 示例 1： 输入： s = "abc", k = 2 输出： 1 解释： s 有三个…
5
题型
5
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们可以使用一个数组 来统计每个字符的出现频率。然后我们对这个数组进行排序，最后返回前 $26 - k$ 个元素的和。 时间复杂度 $O(|\Sigma| \times \log |\Sigma|)$，空间复杂度 ，其中 是字符集的大小，本题中 $|\Sigma| = 26$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个字符串 s（由小写英文字母组成）和一个整数 k。
你的任务是删除字符串中的一些字符（可以不删除任何字符），使得结果字符串中的 不同字符数量 最多为 k。
返回为达到上述目标所需删除的 最小 字符数量。
示例 1：
输入： s = "abc", k = 2
输出： 1
解释：
s有三个不同的字符：'a'、'b'和'c'，每个字符的出现频率为 1。- 由于最多只能有
k = 2个不同字符，需要删除某一个字符的所有出现。 - 例如，删除所有
'c'后，结果字符串中的不同字符数最多为k。因此，答案是 1。
示例 2：
输入： s = "aabb", k = 2
输出： 0
解释：
s有两个不同的字符（'a'和'b'），它们的出现频率分别为 2 和 2。- 由于最多可以有
k = 2个不同字符，不需要删除任何字符。因此，答案是 0。
示例 3：
输入： s = "yyyzz", k = 1
输出： 2
解释：
s有两个不同的字符（'y'和'z'），它们的出现频率分别为 3 和 2。- 由于最多只能有
k = 1个不同字符，需要删除某一个字符的所有出现。 - 删除所有
'z'后，结果字符串中的不同字符数最多为k。因此，答案是 2。
提示：
1 <= s.length <= 161 <= k <= 16s仅由小写英文字母组成。
解题思路
方法一：计数 + 贪心
我们可以使用一个数组 来统计每个字符的出现频率。然后我们对这个数组进行排序，最后返回前 个元素的和。
时间复杂度 ，空间复杂度 ，其中 是字符集的大小，本题中 。
class Solution:
def minDeletion(self, s: str, k: int) -> int:
return sum(sorted(Counter(s).values())[:-k])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to break the problem down into logical steps.
- question_mark
Assess whether they can efficiently implement frequency counting and sorting.
- question_mark
Evaluate their understanding of greedy algorithms and when to apply them.
常见陷阱
外企场景- error
Overcomplicating the problem by attempting unnecessary operations.
- error
Failing to handle edge cases like when the number of distinct characters is already <= k.
- error
Incorrectly deleting characters or not updating the frequency table properly.
进阶变体
外企场景- arrow_right_alt
Consider modifying the problem to handle uppercase letters as well.
- arrow_right_alt
Change the deletion criteria to minimize the number of characters rather than deletions.
- arrow_right_alt
Allow only a fixed number of deletions, and ask how the candidate would adjust the problem to account for this constraint.