288. Minimum Sum of Squares of Character Counts After Removing K Characters

Given a string s and an integer k, you may remove exactly k characters from s, one at a time, choosing freely which character to remove at each step. After the removals, compute the sum of the squares of the remaining count of each distinct character that still appears at least once. Print the minimum possible value of this sum, choosing removals optimally.

Input: The first line contains the string s of lowercase letters. The second line contains the integer k, the number of characters to remove. Output: Print a single integer - the minimum possible sum of squares of the remaining character counts.

1 <= |s| <= 10^5, 0 <= k <= |s|, s consists of lowercase English letters

This is a strong example of 'greedy + heap' as a combined pattern: greedy tells you WHICH choice to make at each step (always the current maximum), and the heap is simply the efficient DATA STRUCTURE that makes finding that choice fast, repeatedly.

You can delete k characters from a string, one at a time, choosing freely each time. After deleting, add up the SQUARE of how many times each remaining letter appears. Minimize that total. Brute force: Try every possible way of distributing k removals across the distinct characters (a combinatorial search) and compute the resulting sum of squares for each distribution, keeping the best - this technically finds the right answer but explodes combinatorially and is far too slow for any non-trivial input. Optimised: Because squaring a count and reducing it by 1 always shrinks the total MORE when applied to the currently-largest count than to any smaller one (the marginal reduction from reducing count c by 1 is 2c - 1, which grows with c), the greedy strategy of always shrinking whichever count is currently largest is provably optimal at every single step - a max-heap makes finding 'the currently largest count' instant at each of the k rounds.

Apply the exact same greedy rule - always remove one occurrence of whichever character currently has the highest count - but maintain the counts in a max-heap instead of rescanning a small array: build the heap once from the character counts, then k times pop the current maximum, decrement it, and push it back if still positive. With only 26 distinct letters the heap and the plain linear scan cost about the same in practice, but the heap is the technique that generalises correctly if the alphabet were much larger or unbounded, which is why it's the standard way this greedy is implemented and matches the problem's 'Heap' tag. Time: O(k log 26) Space: O(1) (heap capped at 26 entries)

Count each character's frequency, then repeat k times: scan the (at most 26) counts to find whichever is currently largest and decrement it by one. This is optimal because the sum of squares is convex - reducing a count c by 1 always shrinks the sum by exactly 2c - 1, and that saving is largest when c is the largest count available, so always taking from the current maximum never does worse than any other choice (a standard greedy-exchange argument). Since the scan is only over the fixed alphabet size, each of the k steps costs a small constant amount of work rather than branching combinatorially. Time: O(k) Space: O(1) (26 counters)

Recursively try every way of spending the k removals across the (at most 26) distinct character counts - at each of the k steps, branch over every character that still has a positive count, decrement it, and recurse - evaluating the sum of squares only once all k removals are made, then take the minimum over every branch explored. This directly matches the problem's definition of 'choose removals to minimise the sum of squares', but branching over up to 26 choices at each of k steps explodes combinatorially and is only feasible for tiny k. Time: O(26^k) Space: O(k) recursion depth

1. Count how many times each distinct character currently appears in the string. 2. Put all these counts into a max-priority-queue (max-heap), so the largest count is always instantly accessible. 3. Repeat k times: pop the largest count, decrease it by exactly one (since you removed one character from that letter), and push the decreased value back in (unless it's now zero). 4. After all k removals, sum the square of every remaining positive count - that total is your minimized answer.

Time: O((distinct characters) + k log(distinct characters)) - building the initial heap is fast, and each of the k removal rounds costs a small, fast heap operation. Space: O(distinct characters) - at most 26 entries for lowercase English letters, completely independent of the string's actual length.

k = 0 (no removals, just the sum of squares of the original counts); k = |s| (every character removed, sum is 0); a string made of a single repeated character; |s| = 10^5 for performance.

Be ready to justify the greedy choice mathematically (the marginal benefit of shrinking a count of c is 2c-1, which is larger for larger c) rather than just asserting 'greedy obviously works' - interviewers specifically probe for this reasoning on greedy-plus-heap problems.