NeetCode #802LC-1647MediumGreedy
← Back to All Problems#802 · #1647 · Minimum Deletions to Make Character Frequencies Unique(字符频次唯一的最小删除次数)
📌 Problem Statement & Constraints
A string
s is good if no two different characters have the same frequency. Return the minimum number of deletions to make s good. Constraints: 1 <= s.length <= 10^5, s consists of lowercase English letters.💡 Core Algorithmic Approaches
- Count the frequency of each character, then sort the frequencies descending.
- Process frequencies from largest to smallest, keeping a set of frequencies already used.
- If a frequency is already taken, decrement it until it is unused (possibly reaching 0), counting each decrement as a deletion.
- Processing the largest first is optimal because shrinking a large frequency never blocks a later one more than necessary.
💻 Benchmark Python3 Implementation
class Solution:
def minDeletions(self, s: str) -> int:
from collections import Counter
freqs = sorted(Counter(s).values(), reverse=True)
used = set()
res = 0
for f in freqs:
while f > 0 and f in used:
f -= 1
res += 1 # one deletion
used.add(f)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + 26^2): counting plus at most 26 shrinks of bounded length.
💾 Space Complexity
O(1): the frequency set is bounded by the alphabet.
⚠️ Interview Pitfalls & Follow-ups
- Refusing to reduce a frequency to 0: deleting all copies of a character is allowed and is sometimes necessary.
- Processing frequencies in ascending order: the greedy must start from the largest to avoid unnecessary deletions.
- Adding 0 to the used set repeatedly: harmless for correctness because a zero-frequency character no longer exists.
- Using a list membership test: it is O(26) per check; a set keeps it constant.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.