How should I practice Letter Candles?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Intuit online assessment problems in FastPrep.

Is Letter Candles associated with Intuit?

FastPrep tags this as a Intuit coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Heap

Letter Candles

Learn this problem

● MediumIntuitOA

Problem statement

Your friend Alice has a box with N letter candles in it. The cost of the box is determined as follows - Find the number of occurrences of each character in the box and sum up the squares of these numbers.

Alice wants to reduce the cost of the box by removing some candles from it. However, she is allowed to remove at most M candles from the box. Can you help Alice determine the minimum cost of the box?

Input

The first line of the input contains the integer N, representing the number of letter candles. The second line of the input contains the integer M, representing the number of candles Alice can remove. The third line of the input contains an N-lettered string S, which contains lowercase English letters, representing the letter candles in the box.

Output

Print the minimum possible cost of the box.

Function

minimumCost(n: int, m: int, s: String) → int

Examples

Example 1

n = 6m = 2s = "bacaac"return = 6

There are two As, one B, and three Cs in the box. Current cost of the box is 2^2 + 1^2 + 3^2 = 14. The best way to minimize the cost of the box is to remove two C-shaped candles from it. The new minimal cost will be 2^2 + 1^2 + 1^2 = 6. The answer is 6.

Example 2

n = 15m = 3s = "xxxxxxxxxxxxxxx"return = 144

There are 15 Xs. The current cost of the box is 15^2 = 225. The only way to minimize the cost is by reducing three X-shaped candles from it. The new minimal cost will be 12^2 = 144. The answer is 144.

Constraints

Unknwon for now. Will add once find them 🛵