Bootcamps
Masterclasses
Menu
Courses
Account
Login / Sign Up

Game with String

Medium Acceptance 53.96% Points 30

Given a string str consisting of lowercase alphabets and a number k, the task is to find the minimum possible value of the string after removing k characters. The value of a string is defined as the sum of the squares of the frequencies of each distinct character in the string. Your goal is to return the minimum value that can be achieved after removing exactly k characters.

Examples
Example 1

image

Input: str = aabbbbcc, k = 2

Output: 12

Explanation: We remove two 'b's from the string to get the updated string "aabcc". The value is calculated as: 'a' occurs 2 times ? 22 = 4. 'b' occurs 2 times ? 22 = 4. 'c' occurs 2 times ? 2^2 = 4. Total value = 4 + 4 + 4 = 12

Example 2

image

Input: str = abc, k = 1

Output: 2

Explanation: We remove one character (e.g., 'a') to get the updated string "bc". The value is calculated as: 'b' occurs 1 time ? 12 = 1. 'c' occurs 1 time ? 12 = 1. Total value = 1 + 1 = 2

Constraints
  • 0 <= k <= |string length| <= 5*10^4
Hints
  • Expected Time Complexity: O(n+klog(p))
  • Expected Auxiliary Space: O(n)
Topics
Heap
Companies
Amazon Walmart Adobe
Added 16 Aug 2026 53.96% acceptance
Ln 1, Col 1Sign in to save your code
aabbbbcc
2
12