What is the main pattern to recognize in Minimum Deletions to Make Character Frequencies Unique?

The key pattern is greedy choice plus invariant validation: always reduce the highest conflicting frequency to achieve uniqueness efficiently.

Can this problem be solved without sorting the frequencies?

Yes, you can use a set to track used frequencies and decrement conflicting frequencies iteratively, avoiding explicit sorting.

Why are characters with zero frequency ignored?

Once a character's frequency reaches zero, it effectively no longer exists in the string, so it doesn't count toward frequency conflicts.

What data structure is best for counting frequencies?

A hash table or dictionary mapping characters to counts is optimal, allowing O(1) updates and lookups for each character.

How does GhostInterview prevent common pitfalls in this problem?

It tracks used frequencies and guides frequency reduction decisions, ensuring minimal deletions and correct handling of zero-frequency cases.

#1647

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

字符频次唯一的最小删除次数

如果字符串 s 中不存在两个不同字符频次相同的情况，就称 s 是优质字符串。给你一个字符串 s ，返回使 s 成为优质字符串需要删除的最小字符数。字符串中字符的频次是该字符在字符串中的出现次数。例如，在字符串 "aab" 中， 'a' 的频次是 2 ，而 'b' 的频次是…

哈希表字符串贪心排序

题目描述

如果字符串 s 中 不存在 两个不同字符频次相同的情况，就称 s 是 优质字符串 。

给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的最小字符数。

字符串中字符的频次是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。

示例 1：

输入：s = "aab"
输出：0
解释：s 已经是优质字符串。

示例 2：

输入：s = "aaabbbcc"
输出：2
解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。

示例 3：

输入：s = "ceabaacb"
输出：2
解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）

提示：

1 <= s.length <= 10⁵
s 仅含小写英文字母

lightbulb

解题思路

方法一：数组 + 排序

我们先用一个长度为 $26$ 的数组 $\textit{cnt}$ 统计字符串 $s$ 中每个字母出现的次数。

然后我们对数组 $\textit{cnt}$ 进行倒序排序。定义一个变量 $\textit{pre}$ 记录当前字母的出现次数。

接下来，遍历数组 $\textit{cnt}$ 每个元素 $v$ ，如果当前 $\textit{pre}$ 等于 $0$ ，我们直接将答案加上 $v$ ；否则，如果 $v \geq \textit{pre}$ ，我们将答案加上 $v-\textit{pre}+1$ ，并且将 $\textit{pre}$ 减去 $1$ ，否则，我们直接将 $\textit{pre}$ 更新为 $v$ 。然后继续遍历下个元素。

遍历结束，返回答案即可。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minDeletions(self, s: str) -> int:
        cnt = Counter(s)
        ans, pre = 0, inf
        for v in sorted(cnt.values(), reverse=True):
            if pre == 0:
                ans += v
            elif v >= pre:
                ans += v - pre + 1
                pre -= 1
            else:
                pre = v
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) to count frequencies plus O(k log k) if sorting frequencies is used, where k is the number of distinct characters; space complexity is O(k) for the frequency map and O(k) for the set of used frequencies.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect a linear scan over the frequency counts with conflict resolution.
question_mark
Watch for edge cases where multiple characters share the same frequency.
question_mark
Check that zero-frequency characters are ignored when validating uniqueness.

warning

常见陷阱

外企场景

error
Failing to decrement frequencies correctly when duplicates exist, leading to overcounted deletions.
error
Not ignoring characters reduced to zero frequency, which can falsely appear as conflicts.
error
Assuming characters must be deleted in input order rather than using a frequency-based greedy reduction.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the minimum insertions to make all character frequencies unique instead of deletions.
arrow_right_alt
Apply the same frequency uniqueness constraint to subsets of the string or sliding windows.
arrow_right_alt
Modify the problem to allow only specific characters to be deleted, testing selective greedy application.

help

常见问题

外企场景

继续练习

#767 重构字符串 #1657 确定两个字符串是否接近 #1604 警告一小时内使用相同员工卡大于等于三次的人