MediumRating 1510

1647. Minimum Deletions to Make Character Frequencies Unique

hash-tablestringgreedysorting

在 LeetCode 上作答 ↗

解題說明

Minimum Deletions to Make Character Frequencies Unique

題目描述：給定一個字串 s，刪除最少的字元使得每個字元的出現頻率都是唯一的（不存在兩個不同字元有相同頻率）。頻率為 0 的字元不計入。

解題思路：

統計每個字元的頻率。
將頻率由大到小排序。
貪心處理：遍歷排序後的頻率，若當前頻率大於等於前一個已確定的頻率，則將其降低至「前一個頻率 - 1」（但不低於 0）。每次降低的差值累加到答案。

核心想法：高頻率的字元盡量保持不變，衝突時往下調整。由大到小處理可以確保每次調整幅度最小。

C++ 解法

複雜度分析

時間複雜度：O(n + 26 log 26) = O(n) — 統計頻率 O(n)，排序固定 26 個元素為常數時間。

空間複雜度：O(1) — 頻率陣列大小固定為 26。

虛擬碼

1. Count frequency of each character in s
2. Sort the 26 frequencies in descending order
3. Set deletions = 0
4. For i from 1 to 25:
   a. If freq[i] == 0, break
   b. If freq[i] >= freq[i-1]:
      - target = max(0, freq[i-1] - 1)
      - deletions += freq[i] - target
      - freq[i] = target
5. Return deletions

其他解法

使用 HashSet O(n)：統計頻率後，用 HashSet 記錄已使用的頻率值。對每個非零頻率，若已存在於 Set 中則逐步減 1 直到找到未使用的值或降至 0。最壞情況內層 while 累計 O(n) 次。

計數排序 O(n)：由於頻率最大為 n，可以用計數排序替代比較排序。對頻率的頻率再做處理，從高到低分配。較複雜但嚴格 O(n)。

延伸思考

如果允許新增字元（而非只能刪除），最少操作次數是多少？
如果要求頻率不僅唯一，還要連續（如 1, 2, 3, ...），最少刪除多少？
如果字元集不限於小寫字母（如 Unicode），演算法需要如何調整？

Minimum Deletions to Make Character Frequencies Unique — CaffeCode