🔗 题目链接：3545. 不同字符数量最多为 K 时的最少删除数
📚 所属题单：灵茶山艾府 · 贪心算法题单 — §1.1 从最小/最大开始贪心
🏷️ 难度：Easy | 难度分：1211
🔖 标签：贪心、哈希表、字符串、排序

📖 题目描述

给你一个字符串 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 <= 16
• 1 <= k <= 16
• s 仅由小写英文字母组成。

💡 思路分析

这题问的是：最少删几个字符，让字符串里最多只剩 k 种不同字符。

换个角度想：如果有 d 种不同字符，而我们只能保留 k 种，那就得淘汰 d - k 种。

要删的字符数最少 → 优先淘汰出现次数最少的字符！

就像公司裁员——先裁人数最少的部门，总裁员人数就最少 😂

举个栗子 🌰

s = "aaabbcc", k = 1

字符频率：a→3, b→2, c→2，共 3 种，要保留 1 种，淘汰 2 种。

按频率从小到大排：[2, 2, 3]

• 淘汰频率 2 的（比如 b）：删 2 个
• 淘汰频率 2 的（比如 c）：删 2 个

总共删 4 个，只剩 aaa，1 种字符 ✅

算法步骤

1. 统计频率：用数组记录每个字符出现次数
2. 排序：把频率从小到大排
3. 贪心淘汰：如果不同字符数 > k，就从频率最小的开始删，累加删除数

✅ 代码实现（Java）

class Solution {
    public int minDeletion(String s, int k) {
        // 第一步：统计每个字符的出现次数
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        // 第二步：把非零频率收集起来，排序
        // 排序后频率最小的在前面，方便优先删除
        Arrays.sort(freq);

        // 第三步：贪心——从频率最小的开始删
        int ans = 0;
        // freq 数组长 26，排序后前面可能有很多 0
        // 非零的个数就是不同字符数
        // 需要淘汰的种类数 = 不同字符数 - k
        for (int i = 0; i < 26; i++) {
            if (freq[i] == 0) continue; // 跳过不存在的字符
            // 还有多少种非零频率的字符？就是 26 - i 种
            int distinct = 26 - i;
            if (distinct <= k) {
                break; // 已经不超过 k 种了，不用再删
            }
            // 删掉当前频率最小的这种字符
            ans += freq[i];
        }
        return ans;
    }
}

📊 复杂度分析

复杂度		说明
⏱️ 时间	O(n + C log C)	n 是字符串长度，C=26 是字母表大小
💾 空间	O©	频率数组，C=26

🔗 参考

• 灵茶山艾府 · 贪心算法题单

🎯 这题的贪心策略非常直观——要裁就裁小的。统计频率、排序、从小到大砍，三步搞定。和上一题 3074（大箱子优先装）异曲同工，只不过这次反过来：频率最小的优先淘汰。