Minimum sum of squares of character counts after removing k characters
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
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);}