Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Choose the minimum frequency that a retained character will have. Every retained frequency must then fall within [low, low + k]. A character appearing fewer than low times cannot be increased, so it must disappear; a character above the interval only needs its excess removed.

Approach

Count each character's frequency. Try every existing frequency as low. For each candidate, delete all occurrences of characters with frequency below low, delete frequency - (low + k) occurrences from characters above low + k, and leave the others unchanged. Return the smallest deletion total.

It is enough to try existing frequencies. Given any feasible retained set, let low be the smallest original frequency among its characters. Raising its permitted frequency interval to start there cannot require more deletions than using a smaller minimum, while that least-frequent character can remain unchanged. Thus some optimum is represented by an enumerated candidate.

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        freq = defaultdict(int)
        for c in word:
            freq[c] += 1

        res = float('inf')
        for low in freq.values():
            des = 0
            for f in freq.values():
                if f < low:
                    des += f
                elif f > low + k:
                    des += f - (low + k)
            res = min(res, des)

        return res

Complexity analysis

Let n = word.length and u be the number of distinct characters. Time: O(n + u^2). Auxiliary space: O(u).