3085. Minimum deletions to make string k-special

Introduction

You are given a string word and an integer k.

We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string.

Here, freq(x) denotes the frequency of the character x in word, and |y| denotes the absolute value of y.

Return the minimum number of characters you need to delete to make word k-special.

Thoughts

• 題目敘述感覺跟字母頻率有關係，可以先建立一個 character-frequency map(每個字母各有多少)
• 要找出刪掉哪些頻率的字母能夠達到題目需求且刪除數量最少。
  • 這裡可以分成兩種case:
  • 假設給定一個合理的頻率區間: [x, x+k]，在此之外的頻率的字母都需移除直到頻率降到這個區間內
    • Case 1: 頻率(f) < x 的字母: 因為只有刪除操作，所以需全部子母移除，需花費(f)
    • Case 2: 頻率(f) > x 的字母: 要把字母頻率扣到 x，所以需花費 (f - x)
  • 接著觀察到因為只有26個字母，所以最多也只有26種頻率會出現
  • 可以直接使用brute forth，嘗試用不同的頻率區間(26種)，每個頻率區間計算不在區間內的字母的cost(26種)
• 時間複雜度: O(n), n為 word長度。26*26常數項可忽略

Solutions

Python

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        # try all frequency and get minimum
        chars = Counter(word)

        freqs = chars.values()

        ans = int(1e17)
        for base_freq in freqs:
            cost = 0
            for ch, freq in chars.items():
                if freq < base_freq:
                    cost += freq
                elif freq > base_freq + k:
                    cost += freq - (base_freq + k)
            ans = min(ans, cost)
        return ans