Proof of correctness
As suggested by the hint, the following result can be used to solve the problem.\n\n*\nLet $new\_word$ be a k-simple word formed after perfoming the minimum num
As suggested by the hint, the following result can be used to solve the problem.\n\n****\nLet $new\\_word$ be a k-simple word formed after perfoming the minimum number of deletions from word. Then there exists a character $c$ in $new\\_word$ that is never deleted. i.e., its frequency in $new\\_word$ is equal to its frequency in $word$\n****\nAssuming that the above result, we can loop over each unique character in $word$ and assume it is the character $c$. Then we compute min deletions required under this assumption. The minimim number of deletions will be the minumum of all these cases.\n\nBut why is the result true?\n\nAssume to the contrary that there does not exist such a $c$. Then every character in $word$ must be deleted at least once to form new word.\n\nNow, contruct any other word, say $better\\_word$, formed by deleting the same characters from $word$ as $new\\_word$, but all character in $new\\_word$ are deleted one less time.\n\nFor example, if the frequencies of characters in $new\\_word$ are \n$$a: 3, b: 4, c: 5$$\nthen the frequencies of character in $better\\_word$ are \n$$a: 4, b: 5, c: 6$$\n\nNow we will show that $better\\_word$ is k-simple. This will result in a contradiction as the number of deletions required to form $better\\_word$ is strictly lesser than the deletions required to form $new\\_word$. Let $\\alpha$ and $\\beta$ be any two characters in $better\\_word$. Note that from our contruction of $better\\_word$ $\\alpha$ and $\\beta$ are also character in $new\\_word$. Now, as $$new\\_word$$ is k-simple, \n\n$|\\text{freq of }\\alpha \\text{ in } new\\_word - \\text{freq of }\\alpha \\text{ in } new\\_word| < k$\n$\\implies |\\text{freq of }\\alpha \\text{ in } new\\_word + 1 - (\\text{freq of }\\beta \\text{ in } new\\_word + 1)| < k$\n$\\implies |\\text{freq of }\\alpha \\text{ in } better\\_word - \\text{freq of }\\beta \\text{ in } better\\_word| < k$\n\nSince $\\alpha$ and $\\beta$ were arbitrary, $better\\_word$ is k-simple.\n\nHence the result must be true. \n\nThe following solution closely mirrors the approach described at the start \n\n# Code\n```\nclass Solution:\n    def minimumDeletions(self, word: str, k: int) -> int:\n        freq = list(Counter(word).values())\n        minDeletions = float("inf")\n        \n        for c in freq:\n            deletions = 0\n            for f in freq:\n                if f > c + k:\n                    deletions += (f - c) - k\n                elif f < c:\n                    deletions += f\n            minDeletions = min(deletions, minDeletions)\n                        \n        return minDeletions\n\n```
['Python3']