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

思路

  • 自解-傻瓜式教学

  • 贪心算法

代码

  • 自解

class Solution {
    public int minDeletion(String s, int k) {
        int count = 0;
        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            int num = s.charAt(i) - 'a';
            if (counts[num] == 0) {
                count++;
            }
            counts[num]++;
        }
        if (count <= k) {
            return 0;
        }
        int result = 0;
        for (int i = 0; i < count - k; i++) {
            int index = -1;
            int min = 100;
            for (int j = 0; j < counts.length; j++) {
                if (counts[j] != 0 && counts[j] < min) {
                    min = counts[j];
                    index = j;
                }
            }
            result += counts[index];
            counts[index] = 0;
        }
        return result;
    }
}

  • 贪心算法

class Solution {
    public int minDeletion(String s, int k) {
        int result = 0;
        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a']++;
        }
        Arrays.sort(counts);
        for (int i = 0; i < 26 - k; i++) {
            result += counts[i];
        }
        return result;
    }
}