Problem Details
Minimum sum of squares of character counts in a given string after removing “k” characters.
Last Updated: 17 Feb, 2021
Minimum sum of squares of character counts in a given string after removing “k” characters.
Easy
Asked in companies
You are given a string S of length N, and a non-negative integer K, your task is to find the minimum sum of squares of unique character counts in the given string S after removing K characters.
Note:
1) The string contains only lowercase English letters.
2) The length of the string is at least 1.
3) It is guaranteed that K <= N.
4) Let S = aab, character count for a is 2 and that of b is 1. So, the sum of squares will be 2^2 + 1^2 = 5.
Input Format:
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers, N and K, as described in the problem statement.
The second line of each test case contains a string S of length N.
Output Format:
For each test case print in a new line, an integer denoting the minimum sum of squares of unique character counts after removing K characters.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 20
1 <= N <= 10^4
1 <= K <= N
Time Limit: 1sec
Approaches
- Form a subset of size K.
- To do so, we can use recursion.
- Initialize a temporary vector to store the indices of the element in a particular subset.
- Initialize a variable, ans to INT_MAX to store the final answer.
- In each recursion call, we do the following:
- Check if the size of the temporary array is equal to the K or not.
- If the size is K, then:
- Traverse through the string, and store the count of characters (whose indices are not in the temporary array) in the frequency array of size 26.
- Traverse the frequency array again and add the square of values of this array to the result.
- Replace ans with the result if, ans is greater than the result.
- Just simply return after these steps.
- If we go at the end of the string then return, because the size of the temporary array is less than K (If not, then we were at the above step) and we don’t have any more characters in the string to remove.
- For each element, there are 2 options.
- Push the current element in the temporary array then call the recursion function again with the next element.
- Do not push the current element in the temporary array and directly call the recursion function again with the next element.
- After the recursion we have the required answer in the variable ans, so print the ans.
- Traverse through the string, and store the count of all characters in the frequency array of size 26.
- Now run a loop K times, at each iteration do the following:
- Sort this frequency array in increasing order.
- Decrement the value of the 25th(last) index of the frequency array by 1.
- Traverse the frequency array again and add the square of values of this array to the result.
- Traverse through the string, and store the count of all characters in the frequency array of size 26.
- Initialize an empty priority queue let it be pq with max-heap properties.
- Push all the elements of the frequency array into pq, so pq contains the frequency of each character in decreasing order.
- Now run a loop to K times, in each iteration do the following:
- Remove the top element of pq and store it in some variable, let say in variable x.
- Decrement the x by 1.
- Push x again into the pq.
- Initialize a variable to 0 for storing the answer, let it be ans.
- Now, run a while loop till pq becomes empty, in each iteration do the following:
- Remove the top element of pq and store it in some variable, let say in variable x.
- Add the square of x to the final ans.
- Finally, return the ans.