O(n) short Java solution. Hash + Max heap


  • 0
    S
    public class Solution {
        public String frequencySort(String s) {
            if (s == null || s.length() == 0) return s;
            int [] hash = new int[256];
            for(int i=0;i<s.length(); i++){
                hash[s.charAt(i)]++;
            }
            
            PriorityQueue<Integer> pq = new PriorityQueue<Integer>(s.length(), (a, b) -> (hash[b] - hash[a]));
            for(int i=0;i<256; i++){
                if(hash[i] > 0)
                    pq.add(i);
            }
            
            StringBuffer sb = new StringBuffer();
            while(!pq.isEmpty()){
                int index = pq.poll();
                for(int i=0;i<hash[index]; i++){
                    sb.append((char)index);    
                }
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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