Minimum sum of squares of character counts in a given string after removing “k” characters.

Easy
0/40
2 upvotes
Asked in companies
AmazonGoogle inc

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5 1
aabac
Sample Output 1:
6
Explanation for sample input 1:
Remove one ‘a’ from the string let us assume we remove 1st a, string becomes abac. So, the answer we get is 2^2 + 1^2 + 1^2  = 6. If we remove any other character than a let say b, so the answer is 3^2 + 0^2 + 1^2  = 10, which is not the minimum.
Sample Input 2:
1
5 3
dabaa
Sample Output 2:
2
Explanation for sample input 2:
Remove three ‘a’ from the string, string becomes db. So, the answer we get is 0^2 + 1^2 + 1^2  = 2. Another possible solution is to remove two ‘a’ and one ‘b’.
Hint

Select a subset of size K and remove these characters from the string which are in the subset.

Approaches (3)
Recursion based approach
  • 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.
Time Complexity

O(2^N * N), where N is the length of the string and K is the number of characters to be removed.

 

2N for making the subset and after forming the subset we need to traverse the string again for the frequency array.

Space Complexity

O(K), where N is the length of the string and K is the number of characters to be removed.

 

We are storing indices of a particular subset of size K, so extra space of k is required.

Code Solution
(100% EXP penalty)
Minimum sum of squares of character counts in a given string after removing “k” characters.
Full screen
Console