3085.成为K特殊字符串需要删除的最少字符数

目标

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

如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j 都成立，则认为 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 特殊字符，计算使得字符串变为 k 特殊字符串最少需要删除多少个字符。

贪心策略：要删就将频次最小的字母全部删掉，关注的是最终的最大与最小频次，如果只删除部分则会使差值变大。

算法步骤如下：

1. 统计字母出现频次（去除掉频次为 0 的）并排序。
2. 从小到大枚举频次最小值 i，需要删掉的字符个数为 Σl + Σ(r - i - k)， 其中 l 表示所有小于 i 的频次，r 表示所有大于 i + k 的频次。
3. 取其最小值。

代码

/**
 * @date 2025-06-21 20:58
 */
public class MinimumDeletions3085 {

    public int minimumDeletions(String word, int k) {
        int res = Integer.MAX_VALUE;
        int[] cnt = new int[26];
        char[] chars = word.toCharArray();
        for (char c : chars) {
            cnt[c - 'a']++;
        }
        Arrays.sort(cnt);
        List<Integer> frequency = new ArrayList<>();
        for (int i : cnt) {
            if (i > 0) {
                frequency.add(i);
            }
        }
        int l = 0;
        int n = frequency.size();
        for (Integer i : frequency) {
            int deletions = l;
            l += i;
            int r = i + k;
            for (int j = n - 1; frequency.get(j) > r; j--) {
                deletions += frequency.get(j) - r;
            }
            res = Math.min(res, deletions);
        }
        return res;
    }

}

性能