1647. Minimum Deletions to Make Character Frequencies Unique

Medium

Description

給定一個字串 s，若沒有兩個不同字元的出現頻率相同，則稱為「好字串」。回傳使 s 變成好字串所需的最少刪除次數。

Example:

Input: s = “aaabbbcc” Output: 2 (刪除兩個 ‘b’ 或兩個 ‘c’)

Intuition#

統計頻率後，從高到低貪心地將重複頻率往下降。

統計每個字元的出現次數
對頻率排序（從大到小）
若當前頻率已被使用，就一直減少直到找到未使用的頻率或變成 0

Approaches#

1: HashSet 檢查#

概念: 用 HashSet 記錄已使用的頻率，有衝突就不斷減一。
時間複雜度: O(n + k^2)，k 為不同字元數（最多 26）
空間複雜度: O(k)

class Solution {
    fun minDeletions(s: String): Int {
        val freq = IntArray(26)
        for (c in s) freq[c - 'a']++

        val used = HashSet<Int>()
        var deletions = 0

        for (f in freq) {
            var cur = f
            while (cur > 0 && cur in used) {
                cur--
                deletions++
            }
            if (cur > 0) used.add(cur)
        }
        return deletions
    }
}

⭐2: 排序 + 貪心#

概念: 將頻率由大到小排序，確保每個頻率嚴格小於前一個（不超過前一個 - 1 且不低於 0）。
時間複雜度: O(n + k log k)
空間複雜度: O(k)

class Solution {
    fun minDeletions(s: String): Int {
        val freq = IntArray(26)
        for (c in s) freq[c - 'a']++
        freq.sortDescending()

        var deletions = 0
        for (i in 1 until 26) {
            if (freq[i] == 0) break
            if (freq[i] >= freq[i - 1]) {
                val target = maxOf(0, freq[i - 1] - 1)
                deletions += freq[i] - target
                freq[i] = target
            }
        }
        return deletions
    }
}

🔑 Takeaways#

Pattern: 頻率去重 — 統計頻率後貪心調整
關鍵技巧: 排序後從高到低處理，每個頻率不超過前一個減一；HashSet 方式更直觀但邏輯相同