Java O(n) solution using Map and PQ


  • 0
    S
    public class Solution {
        
        class Node{
            int size;
            char ch;
            Node(int s, char c){
                size=s;
                ch=c;
            }
        }
        
        public String frequencySort(String s) {
            if(s==null || s.length()==0)
                return s;
            Map<Character,Integer> map = new HashMap<>();
            int len = s.length();
            for(char ch:s.toCharArray()){
                if(!map.containsKey(ch))
                    map.put(ch,0);
                map.put(ch,map.get(ch)+1);
            }
            Queue<Node> pq = new PriorityQueue<>(map.size(),
                new Comparator<Node>() {
                    public int compare(Node a, Node b){
                        return b.size - a.size;
                    }
                });
            for(char str:map.keySet()){
                pq.add(new Node(map.get(str),str));
            }
            StringBuilder sb = new StringBuilder();
            while(!pq.isEmpty()){
                Node n = pq.poll();
                for(int i=0;i<n.size;i++)
                    sb.append(n.ch);
            }
            //System.out.println(sb.toString());
            return sb.toString();
        }
    }
    

Log in to reply
 

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