Hashtable + Priority Queue (Quite intuitive)


  • 0
    P
    import java.util.*;
    
    public class Solution 
    {
        class Element
        {
            int count;
            char c;
            public Element(char c, int count)
            {
                this.c = c;
                this.count = count;
            }
        }
        public String frequencySort(String s) 
        {
            if(s==null || s.length() == 0) return "";
            
            Hashtable<Character, Integer> hash = new Hashtable<Character, Integer>();
            
            for(int i=0; i<s.length();i++)
                hash.put(s.charAt(i), hash.getOrDefault(s.charAt(i),0)+1);
            
            PriorityQueue<Element> pq = new PriorityQueue<Element>(s.length(), new Comparator<Element>()
            {
               public int compare(Element a, Element b)
               {
                    if(a.count>b.count)
                        return -1;
                    else if(a.count==b.count)
                        return 0;
                    else
                        return 1;
               }
            });
            
            for(char key: hash.keySet())
            {
                Element e = new Element(key, hash.get(key));
                pq.offer(e);
            }
            
            StringBuilder sb = new StringBuilder();
            
            while(!pq.isEmpty())
            {
                Element polled = pq.poll();
                for(int i=0; i<polled.count; i++)
                    sb.append(polled.c);
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.