Game-with-String.java

//{ Driver Code Starts
// Initial Template for Java

import java.io.*;
import java.util.*;

class GFG{
    public static void main(String args[])throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(in.readLine());
        while(t-- > 0){
            String s = in.readLine();
            int k = Integer.parseInt(in.readLine());
            
            Solution ob = new Solution();
            System.out.println(ob.minValue(s, k));
        }
    }
}
// } Driver Code Ends


// User function Template for Java

class Solution{
    static int minValue(String s, int k){
        // code here
        Map<Character,Integer> map = new HashMap<>();
        int res = 0;
        
        for(char c : s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for(int i : map.values()){
            q.add(i);
        }
        
        while(k > 0){
            int cur = q.poll();
            q.add(cur - 1);
            k--;
        }
        
        while(!q.isEmpty()){
            int cur = q.poll();
            res += (cur * cur);
        }
        
        return res;
    }
}