Easy

题目描述

给你一个由小写英文字母组成的字符串 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 时，我们需要删除一些字符，使得剩余的不同字符数量不超过 k。

贪心策略分析：

  1. 统计频次：首先统计字符串中每个字符出现的频次。
  2. 贪心选择：为了使删除次数最少，我们应该删除那些出现频次最少的字符。这是因为删除频次少的字符能够以最小的代价减少不同字符的数量。
  3. 排序优化：将各字符的频次按升序排列，然后依次删除频次最小的字符，直到不同字符数量不超过 k。

算法步骤：

  1. 使用哈希表统计每个字符的出现频次
  2. 将所有频次值收集到数组中并排序
  3. 计算需要删除的字符种类数：d = 不同字符数 - k
  4. 如果 d <= 0，说明无需删除，返回 0
  5. 否则，删除前 d 个频次最小的字符，返回它们的频次之和

这种贪心策略是最优的，因为每次删除都选择代价最小的选项。

代码实现

class Solution {
public:
    int minDeletion(string s, int k) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        vector<int> counts;
        for (auto& p : freq) {
            counts.push_back(p.second);
        }
        
        sort(counts.begin(), counts.end());
        
        int distinctChars = counts.size();
        int d = distinctChars - k;
        
        if (d <= 0) {
            return 0;
        }
        
        int deletions = 0;
        for (int i = 0; i < d; i++) {
            deletions += counts[i];
        }
        
        return deletions;
    }
};

class Solution:
    def minDeletion(self, s: str, k: int) -> int:
        from collections import Counter
        
        freq = Counter(s)
        counts = list(freq.values())
        counts.sort()
        
        distinct_chars = len(counts)
        d = distinct_chars - k
        
        if d <= 0:
            return 0
        
        return sum(counts[:d])

public class Solution {
    public int MinDeletion(string s, int k) {
        var freq = new Dictionary<char, int>();
        foreach (char c in s) {
            freq[c] = freq.GetValueOrDefault(c, 0) + 1;
        }
        
        var counts = new List<int>(freq.Values);
        counts.Sort();
        
        int distinctChars = counts.Count;
        int d = distinctChars - k;
        
        if (d <= 0) {
            return 0;
        }
        
        int deletions = 0;
        for (int i = 0; i < d; i++) {
            deletions += counts[i];
        }
        
        return deletions;
    }
}

var minDeletion = function(s, k) {
    const freq = new Map();
    for (let c of s) {
        freq.set(c, (freq.get(c) || 0) + 1);
    }
    
    const counts = Array.from(freq.values());
    counts.sort((a, b) => a - b);
    
    const distinctChars = counts.length;
    const d = distinctChars - k;
    
    if (d <= 0) {
        return 0;
    }
    
    let deletions = 0;
    for (let i = 0; i < d; i++) {
        deletions += counts[i];
    }
    
    return deletions;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m log m)n 是字符串长度，m 是不同字符数量（最多26个），主要消耗在排序
空间复杂度O(m)需要存储字符频次的哈希表和频次数组，m 是不同字符数量