Medium

题目描述

给你一个字符串 word 和一个整数 k。

如果对于字符串中的所有索引 i 和 j，都有 |freq(word[i]) - freq(word[j])| <= k，则我们认为 word 是 k-特殊 的。

这里，freq(x) 表示字符 x 在 word 中的频率，|y| 表示 y 的绝对值。

返回使 word 变为 k-特殊所需删除的最少字符数。

示例 1：

输入: word = "aabcaba", k = 0
输出: 3
解释: 我们可以通过删除 2 个 "a" 和 1 个 "c" 来使 word 变为 0-特殊。因此，word 变为 "baba"，其中 freq('a') == freq('b') == 2。

示例 2：

输入: word = "dabdcbdcdcd", k = 2
输出: 2
解释: 我们可以通过删除 1 个 "a" 和 1 个 "d" 来使 word 变为 2-特殊。因此，word 变为 "bdcbdcdcd"，其中 freq('b') == 2，freq('c') == 3，freq('d') == 4。

示例 3：

输入: word = "aaabaaa", k = 2
输出: 1
解释: 我们可以通过删除 1 个 "b" 来使 word 变为 2-特殊。因此，word 变为 "aaaaaa"，其中每个字母的频率都是 6。

约束条件：

  • 1 <= word.length <= 10^5
  • 0 <= k <= 10^5
  • word 仅由小写英文字母组成。

解题思路

这道题要求使字符串变为 k-特殊，即任意两个字符的频率差不超过 k。

核心思路：

  1. 频率统计：首先统计每个字符的出现频率
  2. 最小频率枚举：关键洞察是，在最终结果中，具有最小频率的字符不需要删除任何字符。我们可以枚举每个可能的最小频率值
  3. 贪心策略：对于确定的最小频率 minFreq，其他字符的处理规则为：
    • 如果频率 < minFreq：删除所有该字符
    • 如果频率 > minFreq + k：删除多余部分，保留 minFreq + k 个
    • 否则：不删除

算法步骤：

  1. 统计所有字符频率并排序
  2. 枚举每个频率作为最小频率的候选
  3. 对于每个候选最小频率，计算需要删除的字符数
  4. 返回所有方案中的最小删除数

时间复杂度为 O(n + m²)，其中 n 是字符串长度，m 是不同字符数量（最多26）。

代码实现

class Solution {
public:
    int minimumDeletions(string word, int k) {
        vector<int> freq(26, 0);
        for (char c : word) {
            freq[c - 'a']++;
        }
        
        vector<int> frequencies;
        for (int f : freq) {
            if (f > 0) {
                frequencies.push_back(f);
            }
        }
        
        sort(frequencies.begin(), frequencies.end());
        
        int minDeletions = INT_MAX;
        
        for (int minFreq : frequencies) {
            int deletions = 0;
            for (int f : frequencies) {
                if (f < minFreq) {
                    deletions += f;
                } else if (f > minFreq + k) {
                    deletions += f - minFreq - k;
                }
            }
            minDeletions = min(minDeletions, deletions);
        }
        
        return minDeletions;
    }
};

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        from collections import Counter
        
        freq = Counter(word)
        frequencies = list(freq.values())
        frequencies.sort()
        
        min_deletions = float('inf')
        
        for min_freq in frequencies:
            deletions = 0
            for f in frequencies:
                if f < min_freq:
                    deletions += f
                elif f > min_freq + k:
                    deletions += f - min_freq - k
            min_deletions = min(min_deletions, deletions)
        
        return min_deletions

public class Solution {
    public int MinimumDeletions(string word, int k) {
        var freq = new int[26];
        foreach (char c in word) {
            freq[c - 'a']++;
        }
        
        var frequencies = new List<int>();
        foreach (int f in freq) {
            if (f > 0) {
                frequencies.Add(f);
            }
        }
        
        frequencies.Sort();
        
        int minDeletions = int.MaxValue;
        
        foreach (int minFreq in frequencies) {
            int deletions = 0;
            foreach (int f in frequencies) {
                if (f < minFreq) {
                    deletions += f;
                } else if (f > minFreq + k) {
                    deletions += f - minFreq - k;
                }
            }
            minDeletions = Math.Min(minDeletions, deletions);
        }
        
        return minDeletions;
    }
}

var minimumDeletions = function(word, k) {
    const freq = {};
    for (let c of word) {
        freq[c] = (freq[c] || 0) + 1;
    }
    
    const frequencies = Object.values(freq).sort((a, b) => a - b);
    
    let minDeletions = Infinity;
    
    for (let minFreq of frequencies) {
        let deletions = 0;
        for (let f of frequencies) {
            if (f < minFreq) {
                deletions += f;
            } else if (f > minFreq + k) {
                deletions += f - minFreq - k;
            }
        }
        minDeletions = Math.min(minDeletions, deletions);
    }
    
    return minDeletions;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + m²)，其中 n 是字符串长度，m 是不同字符数量（最多26）。统计频率需要 O(n)，排序需要 O(m log m)，枚举和计算需要 O(m²)
空间复杂度O(m)，存储字符频率数组，m 最多为 26

相关题目