3545. 不同字符数量最多为 K 时的最少删除数 

English Version

题目描述

给你一个字符串 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 仅由小写英文字母组成。

解法

方法一：计数 + 贪心

我们可以使用一个数组 $\textit{cnt}$ 来统计每个字符的出现频率。然后我们对这个数组进行排序，最后返回前 $26 - k$ 个元素的和。

Python3

class Solution:
    def minDeletion(self, s: str, k: int) -> int:
        return sum(sorted(Counter(s).values())[:-k])

Java

class Solution {
    public int minDeletion(String s, int k) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        Arrays.sort(cnt);
        int ans = 0;
        for (int i = 0; i + k < 26; ++i) {
            ans += cnt[i];
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minDeletion(string s, int k) {
        vector<int> cnt(26);
        for (char c : s) {
            ++cnt[c - 'a'];
        }
        ranges::sort(cnt);
        int ans = 0;
        for (int i = 0; i + k < 26; ++i) {
            ans += cnt[i];
        }
        return ans;
    }
};

Go

func minDeletion(s string, k int) (ans int) {
	cnt := make([]int, 26)
	for _, c := range s {
		cnt[c-'a']++
	}
	sort.Ints(cnt)
	for i := 0; i+k < len(cnt); i++ {
		ans += cnt[i]
	}
	return
}

TypeScript

function minDeletion(s: string, k: number): number {
    const cnt: number[] = Array(26).fill(0);
    for (const c of s) {
        ++cnt[c.charCodeAt(0) - 97];
    }
    cnt.sort((a, b) => a - b);
    return cnt.slice(0, 26 - k).reduce((a, b) => a + b, 0);
}