Crash Code Part-12 (Letter Candles Minimum Cost)

Problem Description & Examples

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 characters 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

• Line 1: Integer N, representing the number of letter candles.
• Line 2: Integer M, representing the number of candles Alice can remove.
• Line 3: 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.

Example Case:

• Input: N=6, M=2, S=bacacc
• Output: 6
• Explanation: There are two As, one B, and three Cs. The current cost is 2^2 + 1^2 + 3^2 = 14. The best way to minimize cost is to remove two C-shaped candles. The new minimal cost will be 2^2 + 1^2 + 1^2 = 6.

Approach & Theory

To minimize the sum of squares, you must greedily reduce the highest frequency character. Reducing a larger number decreases the square sum much more than reducing a smaller number.

Since the string only contains lowercase English letters, there are at most 26 unique characters. We can count the frequencies, extract them into a list, and repeatedly find and decrement the maximum value up to M times.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

import sys
import math
import random
import os

# implement method/function with name 'solve' below.
#
# The function is expected to return a value of type INTEGER.
# The function accepts following parameters:
#  1. N is of type INTEGER.
#  2. M is of type INTEGER.
#  3. S is of type STRING.

def solve(N, M, S):
    # 1. Count the frequencies of each character using a standard dictionary
    counts = {}
    for char in S:
        counts[char] = counts.get(char, 0) + 1

    # Extract just the frequency numbers into a list
    frequencies = list(counts.values())

    # 2. Greedily remove up to M candles
    for _ in range(M):
        if not frequencies:
            break

        # Find the index of the largest frequency
        max_idx = 0
        for i in range(1, len(frequencies)):
            if frequencies[i] > frequencies[max_idx]:
                max_idx = i

        # If the largest frequency is 0, the box is empty
        if frequencies[max_idx] == 0:
            break

        # Remove one candle of the most frequent type
        frequencies[max_idx] -= 1

    # 3. Calculate and return the final minimal cost
    min_cost = 0
    for f in frequencies:
        min_cost += f * f

    return min_cost
if __name__ == '__main__':
  fptr = open(os.enviorn['OUTPUT_FILE_PATH'])
  fptr.write("\n")
  N = int(input().strip())
  M = int(input().strip())
  S = input()
  outcome = solve(N,M,S)
  fptr.write(str(outcome) + '\n');
  fptr.close()

Complexity Analysis

• Time Complexity: O(N + M). Counting string frequencies takes O(N) time. Finding the maximum frequency takes at most 26 operations, repeated M times, which simplifies to O(M).
• Space Complexity: O(1). The dictionary and list store a maximum of 26 integer frequencies, using constant extra memory.