[Python3] DFS + Backtracking
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n##### 1.\n```\nclass Solution:\n    def minimumDeletions(self, word: str, k: int) -> int:\n        c = collections.Counter(word)\n        cnt = sorted(collections.Counter(word).values())\n        res = 0\n        \n        def helper(i: int, j: int) -> int:\n            if i >= j: return 0\n            if cnt[j] - cnt[i] <= k: return 0\n            res = float("inf")\n            ci = cnt[i]\n            cnt[i] = 0\n            res = min(res, helper(i + 1, j) + ci)\n            cnt[i] = ci\n            \n            cj = cnt[j]\n            cnt[j] = cnt[i] + k\n            if cnt[j] == 0:\n                res = min(res, helper(i, j - 1) + cj)\n            else:\n                res = min(res, helper(i, j - 1) + cj - cnt[j])\n            cnt[j] = cj\n            return res\n            \n        return helper(0, len(cnt) - 1)\n```\n\n##### 2. \n\nInspired by lee215\n\n```\nclass Solution:\n    def minimumDeletions(self, word: str, k: int) -> int:\n        cnt = collections.Counter(word).values()\n        res = float("inf")\n        for x in cnt:\n            res = min(res, sum(c if c < x else max(0, c - x -k) for c in cnt))\n        return res\n```
['Python3']