Java Solution | Used PriorityQueue as MaxHeap | No Map used | Complexity O(n + log n + nlogn)


  • 0
    M
    public class Solution {
        
        /**
         * Used Max Heap.
         * In Java Max Heap is implemented using PriorityQueue.
         * However you can create your own custom heap if you want.
         * The objects that are stored on the heap have to implement the Comparable interface
         * making them comparable to each other
         */
        public String frequencySort(String s) {
            
            PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
            
            char[] s_chars = s.toCharArray();
            
            // Sorting char array
            // Complexity : O(nlogn)
            Arrays.sort(s_chars);
            
            // Creating the max heap
            // Complexity : O(n)
            for (int idx = 0; idx < s_chars.length; idx++) {
                
                Pair p = new Pair(s_chars[idx], 0);
                
                while (idx < s_chars.length && s_chars[idx] == p.getCharacter()) {
                    p.setCount(p.getCount() + 1);
                    idx++;
                }
                
                // System.out.println(p.getCharacter() + " : " + p.getCount());
                pq.add(p);
                idx--;
            }
            
            StringBuilder result = new StringBuilder();
            
            while (!pq.isEmpty()) {
                Pair p = pq.remove();
                for (int cnt = p.getCount(); cnt > 0; cnt--) {
                    result.append(""+p.getCharacter());
                } 
            }
            
            return result.toString();
        }
    }
    
    class Pair implements Comparable<Pair> {
        private char c;
        private int count;
        
        Pair(char c, int count) {
            this.c = c;
            this.count = count;
        }
        
        public void setCount(int cnt) {
            this.count  = cnt;
        }
        
        public int getCount() {
            return this.count;
        }
        
        public char getCharacter() {
            return this.c;
        }
        
        public int compareTo(Pair p) {
            if (this.count > p.count) {
                return -1;
            } else if (this.count < p.count) {
                return 1;
            } else {
                if (this.c > p.c) {
                    return 1;
                } else if (this.c < p.c) {
                    return -1;
                } else {
                    return 0;
                }
            }
        }
    }
    

Log in to reply
 

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