Minimum sum of squares of character counts after removing k characters

Medium

Problem

Remove exactly k characters from the string so that the sum of the squares of the remaining character counts is as small as possible. Return that sum.

Example 1

Input:  s = "abccc", k = 1
Output: 6

Remove one c: counts 1, 1, 2 → 1 + 1 + 4.

Also asked as: Minimum sum of squares of character counts in a given string after removing “k” characters

Test cases

Case 1

Input:    "abccc", 1
Expected: 6

Case 2

Input:    "aaab", 2
Expected: 2

Case 3

Input:    "abc", 0
Expected: 3

Case 4

Input:    "aa", 2
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Greedy — always decrement the current max frequency

Time O(k log 26 + n)Space O(1)

Removing a character helps most when taken from the most frequent one (n² − (n−1)² = 2n−1 is largest for large n). Use a max-heap of frequencies, k times.

function minStringValue(s, k) {
const freq = new Array(26).fill(0);
for (const c of s) freq[c.charCodeAt(0) - 97]++;
for (let i = 0; i < k; i++) {
let mx = 0;
for (let j = 1; j < 26; j++) if (freq[j] > freq[mx]) mx = j;
if (freq[mx] === 0) break;
freq[mx]--;
}
return freq.reduce((acc, f) => acc + f * f, 0);
}