7 Line Dynamic Programming Solution using Counter, O(n) runtime.
I and J are restricted by O(26) for each since there is 26 char in the alphabet. So our runtime is O(n) from len(word) = n and spacetime is O(26 * 26) ~ O(1). \
I and J are restricted by O(26) for each since there is 26 char in the alphabet. So our runtime is O(n) from len(word) = n and spacetime is O(26 * 26) ~ O(1). \n# Code\n```\nclass Solution:\n    def minimumDeletions(self, word: str, k: int) -> int:\n        cnt = Counter(word)\n        c = deque(sorted(list(cnt.values())))\n        \n        @cache\n        def dfs(i, j):\n            if c[j] - c[i] <=k: return 0\n            return min(c[i] + dfs(i+1,j), max(0, c[j] - c[i] - k) + dfs(i,j-1))\n        \n        return dfs(0, len(c) -1)\n        \n        \n        \n        \n\n\n            \n        \n```
['Dynamic Programming', 'Python3']