[Leetcode] 3085. Minimum Deletions to Make String K-Special

https://leetcode.com/problems/minimum-deletions-to-make-string-k-special/?envType=daily-question&envId=2025-06-21

initial

i thought maybe sorting based on freq and seeing if there is greedy way

but we dont need to sort. We can check for each freq and assume it is the absolute minimum value that we can have. That assumption means the other frequencies MUST BE in the range of that value +k.

1) if other freq < floorVal, we have no choice but to delete that freq completely
2) if other freq> floorVal +k, then we have to cut some frequency to make it within our range. So other freq-(floorVal+k)
3) else it is within our range

sol

class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        counter= Counter(word)
        count = list(counter.items())
        ans=int(10e19)
        for i in range(len(count)):
            tmp=0
            floorVal = count[i][1]
            for j in range(len(count)):
                if i==j:
                    continue
                val = count[j][1]
                if val<floorVal:
                    tmp+=val
                elif val>floorVal+k:
                    tmp +=val-(floorVal+k)
                else:
                    continue
            ans=min(ans,tmp)
        return ans

                
        

complexity

we are iterating through the keys count of our dictionary so worst case it could be n^2 if words are all unique characters ( or more accurately, the number of unique keys C^2)

n space (or more accurately, the number of unique keys C in our dic)