Minimum Deletions to Make String K-Special

main.md

Question

Approach

I count the frequency of each character in the string. Then I sort these frequencies to facilitate comparison. For each possible target frequency f (taken from any of the observed frequencies), I check how many deletions are needed to make all other character frequencies fall within [f, f + k].

Implementation

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        freq = list(Counter(word).values())
        freq.sort()
        res = float('inf')
        n = len(freq)

        for i in range(n):
            deletions = sum(freq[:i])
            for j in range(i, n):
                if freq[j] > freq[i] + k:
                    deletions += freq[j] - (freq[i] + k)
            res = min(res, deletions)

        return res

Complexities

• Time: O(n log n + m²)
• Space: O(m) for frequency storage