Minimum prefix removal
The long description asks us to find minimum number of chars to be removed so that the diff between any 2 frequencies in word <= k.\n2. Find frequencies with Co
1. The long description asks us to find **minimum** number of chars to be removed so that the diff between any 2 frequencies in `word` <= k.\n2. Find frequencies with Counter/whatever\n3. Now we need to remove minimum chars and satisfy the condition: `|any_freq - any_other_freq| <= k`\n\nLet\'s look at a few examples to figure out how to deal with the problem:\n\nword: `abbcccc`  `k = 0`\nfreq:`1,2,4`\n\nWhat should we remove?\nOptions:\n- we can equalize all the values to minimum value `1`: `1,1,1` will cost us:  `0 + 2-1 + 4-1 = 4`\n- we can remove `1` and equalize all the rest values to minimum value `2`: `0,2,2` will cost us:  `1 + 2-2 + 4-2 = 3`. Which is better\n- we can remove `2` and equalize all the rest values to minimum value `1`: `1,0,1` will cost us:  `0 + 2-0 + 4-3 = 3`. Which is also good.\n\nFrom the above:\n- it does not make sense to remove biggest numbers as it leads to more removals (greedy)\n- removing minimum value and equalizing suffix values to `x <= k` should be the optimzal strategy\n\nCounter example to **remove single minimum** value:\n\nword: `aabbcccccccccddddddddd`  `k = 2`\nfreq:`2,2,9,9`\n\nWhat should we remove?\nOptions:\n- we can equalize all the values to minimum value `2`: `2,2,2,2` will cost us: `14`\n- we can remove the first `2` and equalize all the values to minimum value `2`: `0,2,2,2` will cost us: `16`\n- we can remove the first  and second `2` and equalize all the values to minimum value `9`: `0,0,9,9` will cost us: `4`\n\nFrom the above:\n- we can see that it\'s best to remove the **minimum** prefix_sum and find **minimum** removals needed in the suffix\n\n```\nclass Solution:\n    def minimumDeletions(self, word: str, k: int) -> int:\n        """\n        k-special: |f[i] - f[j]| <= k  0 <= i,j < N\n        \n        ret min # chars to delete to make w k-special\n        \n        aabcaba  k = 0\n        \n        421 -> 111 -> 3+1=4\n        421 -> 22 = 2+1=3\n        \n        124 -> 022\n        1235 -> 1233 -> 2\n        \n        16 -> 06\n        \n        129: 022=7 vs 111=9\n        \n        2299 -> 0099=4 vs 2222=14 \n        min(remove prefix + equalize <= k)\n        """\n        freq = Counter(word)\n        freq = sorted(freq.values())\n        N = len(freq)\n        res = inf\n        for i in range(N):\n            prefix = sum(freq[:i] or [0])\n            suffix = 0\n            for j in range(i + 1, N):\n                diff = freq[j] - freq[i]\n                if diff > k:\n                    suffix += diff - k\n            res = min(res, prefix + suffix)\n        return res\n\t\t\n\t\t# which is the same as\n        freq = sorted(Counter(word).values())\n        N = len(freq)\n        res = inf\n        prefix = 0\n        for i in range(N):\n            res = min(res, prefix + sum(max(0, freq[j] - freq[i] - k) for j in range(i + 1, N)))\n            prefix += freq[i]\n        return res\n\n```
['Prefix Sum', 'Python', 'Python3']