⚡Flashcard Drill➔
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

  1. Count the frequency of each character, then sort the frequencies descending.
  2. Process frequencies from largest to smallest, keeping a set of frequencies already used.
  3. If a frequency is already taken, decrement it until it is unused (possibly reaching 0), counting each decrement as a deletion.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems