Python: frequencies of characters, linear solution
Intuition\n\nIt is clear that the string does not matter and you need to calculate the frequencies of each characters and sort them.\n\nLets assume that your ar
# Intuition\n\nIt is clear that the string does not matter and you need to calculate the frequencies of each characters and sort them.\n\nLets assume that your array is `1, 3, 5, 5, 7, 8, 9, 11, 14` and `k = 4`.\n\nIf you start at position `2`, then you need to remove all the frequencies below this position (cost will be 1 + 3) and then decrease all the frequencies above `5 + k` to this value (cost will be `11 - 9 + 14 - 9`). You do not even need to do this efficiently as array is 32 characters, but you can do this in log linear time (for array of arbitrary size)\n\n# Complexity\n- Time complexity: $O(n)$\n- Space complexity: $O(1)$\n\n# Code\n```\nclass Solution:\n\n  def minimumDeletions(self, word: str, k: int) -> int:\n    arr = sorted(list(Counter(word).values()))\n    suffix_sum = [0] * (len(arr) + 1)\n    for i in range(len(arr) - 1, -1, -1):\n      suffix_sum[i] = suffix_sum[i + 1] + arr[i]\n\n    curr_sum, res = 0, float(\'inf\')\n    for i in range(len(arr)):\n      pos = bisect_right(arr, arr[i] + k)\n      num_left = len(arr) - pos\n\n      tmp = suffix_sum[pos] - num_left * (arr[i] + k) + curr_sum\n      res = min(res, tmp)\n      curr_sum += arr[i]\n    \n    return res\n```
['Python']