JAVA O(N * log(N)) solution using HashMap and PriorityQueue, with customized class, easy to understand


  • 1
    M
    public class Solution {
        // customized class Char to store some useful info
        private class Char {
            public char ch;
            public int freq;
            public PriorityQueue<Char> pq;
            public Char(char ch, PriorityQueue<Char> pq) {
                this.ch = ch;
                freq = 1;
                this.pq = pq;
                pq.offer(this);
            }
            // method to advance one freq on this char
            public void addOneFreq() {
                pq.remove(this);
                freq += 1;
                pq.offer(this);
            }
            // to string
            public String toString() {
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i < freq; i++) {
                    sb.append(ch);
                }
                return sb.toString();
            }
        }
        public String frequencySort(String s) {
            if(s == null || s.length() == 0) return "";
            Map<Character, Char> map = new HashMap<>();
            // max heap
            PriorityQueue<Char> pq = new PriorityQueue<>(1, (x1, x2) -> x2.freq - x1.freq);
            // O(nlog(n)) -> n chars in s, pq.offer in "new Char()" cost log(n) and addOneFreq() cost log(n)
            for(char ch : s.toCharArray()) {
                if(map.containsKey(ch)) {
                    map.get(ch).addOneFreq();
                }
                else {
                    map.put(ch, new Char(ch, pq));
                }
            }
            StringBuilder res = new StringBuilder();
            // O(nlog(n)) -> n nodes in pq, poll() cost log(n)
            while(!pq.isEmpty()) {
                res.append(pq.poll().toString());
            }
            return res.toString();
        }
    }
    

Log in to reply
 

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