What is a k-special string?

A k-special string is one where the absolute frequency difference between any two characters is at most k.

How do I solve the 'Minimum Deletions to Make String K-Special' problem?

The problem is solved by counting the frequencies of characters, sorting them, and using a greedy strategy to delete characters and meet the k-special condition.

What pattern is used in solving the 'Minimum Deletions to Make String K-Special' problem?

The problem uses a greedy approach combined with invariant validation, focusing on minimizing deletions based on character frequencies.

What is the time complexity of the 'Minimum Deletions to Make String K-Special' problem?

The time complexity is O(n + C^2), where n is the length of the string and C is the number of distinct characters.

Can the 'Minimum Deletions to Make String K-Special' problem be solved using dynamic programming?

No, the problem is best solved with a greedy strategy, using frequency counting and validation rather than dynamic programming.

#3085

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个字符串 word 和一个整数 k 。如果 |freq(word[i]) - freq(word[j])| 对于字符串中所有下标 i 和 j 都成立，则认为 word 是 k 特殊字符串。此处， freq(x) 表示字符 x 在 word 中的出现频率，而 |y| 表示 y 的绝对值…

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

题目描述

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

lightbulb

解题思路

方法一：计数 + 枚举

我们可以先统计字符串中每个字符的出现次数，将所有次数放入数组 $nums$ 中，由于题目中字符串只包含小写字母，所以数组 $nums$ 的长度不会超过 $26$ 。

接下来，我们可以枚举在 $[0,..n]$ 的范围内枚举 $K$ 特殊字符串中的字符最小频率 $v$ ，然后用一个函数 $f(v)$ 来计算将所有字符的频率调整为 $v$ 的最小删除次数，最后取所有 $f(v)$ 的最小值即为答案。

函数 $f(v)$ 的计算方法如下：

遍历数组 $nums$ 中的每个元素 $x$ ，如果 $x \lt v$ ，则说明我们需要将出现次数为 $x$ 的字符全部删除，删除次数为 $x$ ；如果 $x \gt v + k$ ，则说明我们需要将出现次数为 $x$ 的字符全部调整为 $v + k$ ，删除次数为 $x - v - k$ 。累加所有删除次数即为 $f(v)$ 的值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        def f(v: int) -> int:
            ans = 0
            for x in nums:
                if x < v:
                    ans += x
                elif x > v + k:
                    ans += x - v - k
            return ans

        nums = Counter(word).values()
        return min(f(v) for v in range(len(word) + 1))

speed

复杂度分析

指标	值
时间	O(n + C^2)
空间	O(C)

psychology

面试官常问的追问

外企场景

question_mark
Understand frequency counting and its importance for this problem.
question_mark
Demonstrate ability to apply a greedy strategy to optimize deletions.
question_mark
Check for a valid approach by maintaining the invariant while making deletions.

warning

常见陷阱

外企场景

error
Not using a hash table for efficient frequency counting can lead to slower solutions.
error
Forgetting to sort the frequencies might result in suboptimal deletions.
error
Incorrectly applying the greedy approach might lead to an invalid final string.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of minimizing deletions, the problem could be framed as maximizing the number of characters that remain in the string.
arrow_right_alt
The problem could involve different limits on k or the size of the string, testing the solution's scalability.
arrow_right_alt
Instead of just deletions, the problem could also involve transforming characters to meet the k-special condition.

help

常见问题

外企场景

继续练习

#3081 替换字符串中的问号使分数最小 #3035 回文字符串的最大数量 #3016 输入单词需要的最少按键次数 II