Suppose we select several characters as the final answer, and let x be the character with the smallest frequency in the answer. It can be shown that out of the selected characters, the optimal solution will never delete an occurrence of character x to obtain the answer.
提示 3
We will fix a character c and assume that it will be the character with the smallest frequency in the answer. Suppose its frequency is x.
提示 4
Then, for every other character, we will count the number of occurrences that will be deleted. Suppose that the current character has y occurrences.
If y < x, we need to delete all of them.
if y > x + k, we should delete y - x - k of such character.
