class Solution {
    
    // Greedy solution implementing PriorityQueue
        
    public int minDeletions(String s) {
        int maxChar = 25;
        HashMap<Character, Integer> freq = new HashMap(maxChar);
        PriorityQueue<Integer> pq = new PriorityQueue(maxChar, new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });
        
        // Characters to delete
        int delCount = 0; 
        
        // Add characters to Map
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            
            if(!freq.containsKey(c))
                freq.put(c, 1);
            else
                freq.put(c, freq.get(c) + 1);
        }
        
        //for(Map.Entry entry : freq.entrySet())
            //System.out.println(entry.getKey() + ":" + entry.getValue());
        
        // Add character frequencies to PriorityQueue
        for(Map.Entry entry : freq.entrySet())
            pq.add((Integer) entry.getValue());
        
        
        // Traverse PriorityQueue
        while(!pq.isEmpty()){
            
            //printQ(pq);
            
            // store topmost entry
            int top = pq.peek();
            // remove topmost entry
            pq.remove();
            
            if(pq.isEmpty())
                break;
            
            if(top == pq.peek()){
                if(top > 1)
                    // insert decremented top entry
                    pq.add(top - 1);
                // increment character deletion count
                delCount++;
            }
        }
         
        return delCount;
    }
    
    public void printQ(PriorityQueue<Integer> pq){
        for(Integer i : pq)
            System.out.print(i +",");
        System.out.println();
    }
}