Candle Box Cost

The first line of input contains the integer N, the initial number of candles.
The second line contains the integer M, the maximum number of candles you can remove.
The third line contains the N-letter string S.

Print a single integer representing the minimum achievable cost.

The key insight is to use a greedy strategy. The reduction in cost is greatest when you remove a candle from the character group that is currently the most frequent.
A priority queue (max-heap) is the ideal data structure to efficiently find the most frequent character group at each step of the removal process.

Sample Input 1:

4
1
abcc

Sample Output 1:

3

Explanation for Sample 1:

The string is "abcc". Frequencies are a=1, b=1, c=2.
Initial cost = 1^2 + 1^2 + 2^2 = 1 + 1 + 4 = 6.
We can remove M=1 candle. To get the biggest cost reduction, we should remove a candle from the most frequent group, which is 'c'.
After removing one 'c', the new frequencies are a=1, b=1, c=1.
The minimum cost is 1^2 + 1^2 + 1^2 = 3.

Sample Input 2:

7
3
aaabbbc

Sample Output 2:

6

Explanation for Sample 2:

Initial frequencies: {a:3, b:3, c:1}. Initial Cost = 3^2+3^2+1^2 = 19.
We have M=3 removals.
- Removal 1: Frequencies are {a:3, b:3, c:1}. Pop 3 (for 'a'). Push 2 back. Heap is now {3, 2, 1}.
- Removal 2: Frequencies are {b:3, a:2, c:1}. Pop 3 (for 'b'). Push 2 back. Heap is now {2, 2, 1}.
- Removal 3: Frequencies are {a:2, b:2, c:1}. Pop 2 (for 'a'). Push 1 back. Heap is now {2, 1, 1}.
Final counts are 2, 1, 1. Minimum cost = 2^2 + 1^2 + 1^2 = 4 + 1 + 1 = 6. Wait, my math... `7`...
Ah, after removal 3, the heap can be `{b:2, a:1, c:1}` or `{a:2, b:1, c:1}`. Let's check my trace.
Heap: {3,3,1}. M=3.
1. Pop 3, push 2. Heap {3,2,1}. M=2.
2. Pop 3, push 2. Heap {2,2,1}. M=1.
3. Pop 2, push 1. Heap {2,1,1}. M=0.
Final counts: {2,1,1}. Cost = 4+1+1=6.

Expected Time Complexity:

The expected time complexity is O(N+M*log(UniqueChars)).

Constraints:

1 <= N <= 10^5
0 <= M <= N
`S` consists of lowercase English letters.

Time limit: 1 sec