Medium

题目描述

如果字符串 s 中不存在两个不同字符具有相同的频次，那么称字符串 s 是好 字符串。

给你一个字符串 s，返回使 s 成为好 字符串所需要的最少字符删除次数。

字符串中字符的频次 是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1。

示例 1：

输入：s = "aab"
输出：0
解释：s 已经是好字符串了。

示例 2：

输入：s = "aaabbbcc"
输出：2
解释：你可以删除两个 'b' ，得到好字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ，得到好字符串 "aaabbc" 。

示例 3：

输入：s = "ceabaacb"
输出：2
解释：你可以删除两个 'c' ，得到好字符串 "eabaab" 。
注意，我们只关心结果字符串中仍然存在的字符（即，频次为 0 的字符会被忽略）。

提示：

  • 1 <= s.length <= 10^5
  • s 仅含小写英文字母

解题思路

这道题要求使每个字符的频次都不相同，我们需要通过删除字符来实现。

核心思路：

  1. 统计频次：首先统计每个字符在字符串中的出现频次
  2. 贪心策略：为了删除最少的字符，我们应该尽可能保留频次高的字符，对频次低的字符进行调整
  3. 频次调整：将所有字符按频次从大到小排序，然后依次处理每个字符，确保当前字符的频次不与之前处理过的字符频次相同

具体算法：

  • 使用哈希表统计每个字符的频次
  • 将频次值存入数组并排序（降序）
  • 遍历排序后的频次数组，对于每个频次，如果它与前一个频次相同或更大，就将其减少到前一个频次减1（但不能小于0）
  • 累计需要删除的字符数量

时间复杂度分析： 统计频次O(n)，排序O(26log26)≈O(1)，总体O(n) 空间复杂度分析： 使用哈希表存储频次，O(26)≈O(1)

代码实现

class Solution {
public:
    int minDeletions(string s) {
        vector<int> freq(26, 0);
        for (char c : s) {
            freq[c - 'a']++;
        }
        
        sort(freq.begin(), freq.end(), greater<int>());
        
        int deletions = 0;
        int maxAllowed = freq[0];
        
        for (int i = 0; i < 26; i++) {
            if (freq[i] == 0) break;
            if (freq[i] > maxAllowed) {
                deletions += freq[i] - maxAllowed;
                freq[i] = maxAllowed;
            }
            maxAllowed = max(0, freq[i] - 1);
        }
        
        return deletions;
    }
};

class Solution:
    def minDeletions(self, s: str) -> int:
        from collections import Counter
        
        freq = list(Counter(s).values())
        freq.sort(reverse=True)
        
        deletions = 0
        max_allowed = freq[0]
        
        for i in range(len(freq)):
            if freq[i] > max_allowed:
                deletions += freq[i] - max_allowed
                freq[i] = max_allowed
            max_allowed = max(0, freq[i] - 1)
        
        return deletions

public class Solution {
    public int MinDeletions(string s) {
        int[] freq = new int[26];
        foreach (char c in s) {
            freq[c - 'a']++;
        }
        
        Array.Sort(freq, (a, b) => b.CompareTo(a));
        
        int deletions = 0;
        int maxAllowed = freq[0];
        
        for (int i = 0; i < 26; i++) {
            if (freq[i] == 0) break;
            if (freq[i] > maxAllowed) {
                deletions += freq[i] - maxAllowed;
                freq[i] = maxAllowed;
            }
            maxAllowed = Math.Max(0, freq[i] - 1);
        }
        
        return deletions;
    }
}

var minDeletions = function(s) {
    const freq = new Array(26).fill(0);
    for (let c of s) {
        freq[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    freq.sort((a, b) => b - a);
    
    let deletions = 0;
    let maxAllowed = freq[0];
    
    for (let i = 0; i < 26; i++) {
        if (freq[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)统计字符频次需要O(n)，排序26个元素为O(1)
空间复杂度O(1)只使用固定大小的数组存储26个字母的频次

相关题目