1. 题目解析与贪心算法概述3545题要求我们找到使字符串中不同字符数量不超过K时需要删除的最少字符数。这类字符串操作问题在算法面试中非常常见通常考察对数据结构的选择和算法策略的应用能力。1.1 问题重述给定一个字符串s和整数K我们需要通过删除某些字符使得剩下的字符串中不同字符的数量不超过K。要求找到需要删除的最少字符数。示例 输入s aabbcc, K 2 输出2 解释可以删除两个c得到aabb其中不同字符数为2a和b1.2 贪心算法思想贪心算法在每一步选择中都采取当前状态下最优的选择从而希望导致全局最优解。对于这个问题我们的贪心策略是统计每个字符的出现频率优先保留出现次数多的字符从出现次数少的字符开始删除这种策略之所以有效是因为要最小化删除的字符数我们应该尽量保留那些出现次数多的字符这样需要删除的字符总数才会最少。2. 解决方案设计与实现2.1 算法步骤详解统计字符频率使用哈希表统计字符串中每个字符出现的次数排序频率将统计结果按出现次数从小到大排序计算最小删除数初始化删除计数器delete_count 0初始化当前不同字符数diff_chars 哈希表大小遍历排序后的频率列表当diff_chars K时删除当前字符将其频率减到0delete_count增加该字符的频率diff_chars减12.2 Java实现代码import java.util.*; class Solution { public int minDeletions(String s, int k) { // 统计字符频率 MapCharacter, Integer freqMap new HashMap(); for (char c : s.toCharArray()) { freqMap.put(c, freqMap.getOrDefault(c, 0) 1); } // 将频率存入列表并排序 ListInteger frequencies new ArrayList(freqMap.values()); Collections.sort(frequencies); int deletions 0; int uniqueChars frequencies.size(); int i 0; while (uniqueChars k) { // 总是尝试删除频率最小的字符 int currentFreq frequencies.get(i); deletions currentFreq; uniqueChars--; i; } return deletions; } }2.3 复杂度分析时间复杂度O(n m log m)其中n是字符串长度m是不同字符数量统计频率O(n)排序频率O(m log m)计算删除数O(m)空间复杂度O(m)用于存储字符频率3. 优化与边界情况处理3.1 算法优化上述基础实现可以进一步优化使用数组代替哈希表统计频率当字符集有限时如仅小写字母使用优先队列最小堆来避免排序优化后的实现public int minDeletionsOptimized(String s, int k) { int[] freq new int[26]; for (char c : s.toCharArray()) { freq[c - a]; } PriorityQueueInteger minHeap new PriorityQueue(); for (int count : freq) { if (count 0) { minHeap.offer(count); } } int deletions 0; while (minHeap.size() k) { deletions minHeap.poll(); } return deletions; }3.2 边界情况处理需要考虑的特殊情况字符串为空或nullK为0需要删除所有字符字符串本身不同字符数已经≤K所有字符都相同但K0边界情况处理代码public int minDeletionsWithEdgeCases(String s, int k) { if (s null || s.length() 0) return 0; if (k 0) return s.length(); int[] freq new int[26]; int uniqueChars 0; for (char c : s.toCharArray()) { if (freq[c - a] 0) uniqueChars; freq[c - a]; } if (uniqueChars k) return 0; PriorityQueueInteger minHeap new PriorityQueue(); for (int count : freq) { if (count 0) { minHeap.offer(count); } } int deletions 0; while (minHeap.size() k) { deletions minHeap.poll(); } return deletions; }4. 测试用例与验证4.1 典型测试用例public static void main(String[] args) { Solution solution new Solution(); // 测试用例1基本示例 System.out.println(solution.minDeletions(aabbcc, 2)); // 输出2 // 测试用例2所有字符相同 System.out.println(solution.minDeletions(aaaaa, 1)); // 输出0 // 测试用例3需要删除所有字符 System.out.println(solution.minDeletions(abcde, 0)); // 输出5 // 测试用例4无需删除 System.out.println(solution.minDeletions(aab, 2)); // 输出0 // 测试用例5复杂情况 System.out.println(solution.minDeletions(aaabbbcccdddeee, 3)); // 输出6 }4.2 测试策略功能测试验证算法是否能正确处理常规输入边界测试测试空字符串、K0等特殊情况性能测试测试长字符串下的执行效率随机测试生成随机字符串验证算法正确性5. 算法变种与扩展5.1 类似问题最少删除使字符频率唯一删除最少数量的字符使所有字符频率唯一最多K个不同字符的最长子串找到包含最多K个不同字符的最长子串重组字符串使相同字符不相邻通过删除和重新排列字符使相同字符不相邻5.2 扩展思考如果问题改为可以通过删除或替换字符使得不同字符数不超过K时的最小操作数该如何解决这种情况下替换操作可能比删除更优算法需要相应调整。6. 实际应用场景这类字符串处理算法在实际中有广泛的应用数据压缩通过减少不同字符数量来提高压缩效率文本分析在自然语言处理中控制词汇多样性系统设计限制资源标识符的字符种类数量游戏开发处理玩家输入的字符限制7. 性能优化进阶对于非常大的字符串长度10^6我们可以进一步优化使用计数排序因为字符频率范围有限可以用O(n)排序并行处理多线程统计字符频率流式处理对于无法全部加载到内存的超大字符串优化后的频率统计int[] freq new int[26]; s.chars().parallel().forEach(c - freq[c - a]);8. 常见错误与调试技巧8.1 常见错误忘记处理K0的情况错误计算不同字符数量排序方向错误应该升序而非降序没有考虑字符串为空的情况8.2 调试技巧打印中间结果频率统计、排序后的列表使用小测试用例手动验证检查循环终止条件验证删除计数的累加逻辑提示在面试中即使时间紧张也应该先处理边界情况并向面试官说明这往往比直接写核心逻辑更能展示全面的编程思维。9. 算法证明与正确性分析为了证明贪心算法的正确性我们需要说明最优子结构问题的最优解包含子问题的最优解贪心选择性质通过局部最优选择能达到全局最优在本问题中每次选择删除出现次数最少的字符可以保证为后续选择保留更多字符不会存在一种情况保留某个低频字符而删除高频字符能得到更优解通过数学归纳法可以证明这种策略的正确性10. 不同语言实现对比虽然我们使用Java实现但了解其他语言的实现方式有助于拓宽思路Python实现更简洁from collections import Counter import heapq def minDeletions(s, k): freq Counter(s) if len(freq) k: return 0 min_heap list(freq.values()) heapq.heapify(min_heap) deletions 0 while len(min_heap) k: deletions heapq.heappop(min_heap) return deletionsC实现更高性能#include vector #include unordered_map #include queue int minDeletions(std::string s, int k) { std::unordered_mapchar, int freq; for (char c : s) freq[c]; std::priority_queueint, std::vectorint, std::greaterint min_heap; for (auto pair : freq) min_heap.push(pair.second); int deletions 0; while (min_heap.size() k) { deletions min_heap.top(); min_heap.pop(); } return deletions; }