Short explanation + Comments || 87ms Solution || Using 2-Dimensional DP || O(N) time and O(1) space
Approach\n Describe your approach to solving the problem. \nFirst, calculate frequencies of all the characters.\n\nObservation - For each pair of indices in the
# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst, calculate frequencies of all the characters.\n\nObservation - For each pair of indices in the frequency array, we can either delete all characters of the lower frequency, or reduce just enough characters of the higher frequency as to make their difference = k. \nTo optimise the solution, we can first sort the frequencies and use two pointers `i` and `j` that begin from outside and move in. We can be assured that as soon as we reach the pair of indices whose difference is less than or equal to `k`, all other pairs of indices `p` and `q`, where `i <= p,q <= j `, their difference will be less than k.\n\nSince for each operation, we have two options, either of which can yield correct results, DP can prove to be an effective way to go with.\n\n# Complexity\n- Time complexity: O(N)\nO(N) to calculate frequency + O(C) to sort + O(C) for the memoization logic, where C = number of distinct characters (which can be 26 at max) and N = size of the input string.\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> \n\n- Space complexity: O(1)\nO(26) to store frequency + O(26) for recursive stack.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minimumDeletions(self, word: str, k: int) -> int:\n        d = Counter(word)\n        self.memo = {}\n        freq = sorted(list(d.values()))                         #sort frequencies\n        return self.f(0,len(freq)-1, k, freq)\n\n    def f(self, i, j, k, freq):\n        #if the difference between max and min frequencies <= k, then all frequencies would be at most k distance apart.\n        if abs(freq[i] - freq[j]) <= k:            \n            return 0\n\n        if (i,j) not in self.memo:\n            a = b = float(\'inf\')\n            a = freq[i] + self.f(i+1, j,k, freq)                #either delete all characters of smaller frequency\n            b = freq[j] - freq[i] - k + self.f(i,j-1,k,freq)    #or remove just enough characters of higher frequency as to make difference = k\n                                                                #shift edges i or j accordingly\n            self.memo[(i,j)] = min(a,b)                         #memoize the result for future.\n        return self.memo[(i,j)]\n        \n        \n```\n\n# If you made this far, might as well drop a like :D
['Python3']