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

标签: 贪心 哈希表 字符串 计数 排序

难度: Medium

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

Submission

运行时间: 67 ms

内存: 16.3 MB

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:

        cnt = sorted(word.count(ch) for ch in "abcdefghijklmnopqrstuvwxyz" if ch in word)

        m = len(cnt) - 1
        right = m
        removes = len(word)
        ans = inf
        for left in range(m, -1, -1):
            removes -= cnt[left]
            target = cnt[left] + k
            while right > left and cnt[right] > target:
                removes += cnt[right]
                right -= 1
            res = removes - (m - right) * target
            if ans > res: ans = res
        return ans

Explain

该题解首先统计了字符串中每个字符的频率，并将频率进行排序。对于每个可能的目标频率（从最大频率递减到最小频率），算法尝试确定以该频率为边界时，将所有大于此频率加k的字符频率减少到该边界，所有小于此频率的字符频率提升到该边界需要删除的最少字符数。通过右指针从高频向低频移动，计算每个位置需要删除的字符总数，并不断更新最小删除数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:

        # 统计字符频率并排序
        cnt = sorted(word.count(ch) for ch in 'abcdefghijklmnopqrstuvwxyz' if ch in word)

        # 初始化指针和变量
        m = len(cnt) - 1
        right = m
        removes = len(word)
        ans = float('inf')
        # 从高频到低频遍历所有可能的目标频率
        for left in range(m, -1, -1):
            removes -= cnt[left]
            target = cnt[left] + k
            # 调整右指针使其不超过目标频率
            while right > left and cnt[right] > target:
                removes += cnt[right]
                right -= 1
            # 计算当前目标频率下的最小删除数
            res = removes - (m - right) * target
            # 更新最小删除数
            if ans > res: ans = res
        return ans

Explore

题解的算法在实际执行时并没有直接增加字符的总数，而是通过计算需要删除的最少字符数来模拟这个过程。即使实际上不可能有足够的字符来提升到目标频率，算法所做的是通过计算如果要达到那个频率需要删除多少字符来达成条件。因此，算法主要关注的是达到一个平衡状态下需要删除的字符数量，而非字符数量是否足够。

题解中的算法设计是使 right 指针停在第一个小于或等于目标频率的位置。因此，如果有字符的频率正好等于目标频率加k，这些字符的频率不需要调整，也不会影响删除数的计算。right 指针在这种情况下会停在这些字符的频率之前的位置，只关注那些频率高于目标频率加k的字符。

从最高频率到最低频率遍历可以更快地找到需要删除字符最少的情况。考虑到通常较高频率的字符在减少到较低频率时需要删除的字符数量会更多，从高到低遍历可以快速地评估减少这些高频字符带来的效果，并逐步考虑增加低频字符的影响。这种方法比从低频率开始更高效，因为从低频率开始则需要频繁考虑如何减少高频字符，这在初期可能导致大量不必要的删除操作。