Easy to understand Java Solution with HashMap and MaxQueue


  • 0
    R
    public class Solution {
        public String frequencySort(String s) {
            Map<Character, Integer> freqCnt = new HashMap<>();
            PriorityQueue<Item> maxHeap = new PriorityQueue<>(new Comparator<Item>() {
               @Override
               public int compare(Item o1, Item o2) {
                   return o2.freq - o1.freq;
               }
            });
            StringBuilder sb = new StringBuilder();
            // count the frequency of each character
            for (char c : s.toCharArray()) {
                freqCnt.put(c, freqCnt.getOrDefault(c, 0) + 1);
            }
            // build the MaxHeap
            for (Map.Entry<Character, Integer> entry : freqCnt.entrySet()) {
                maxHeap.offer(new Item(entry.getKey(), entry.getValue()));
            }
            // build the string
            while (!maxHeap.isEmpty()) {
                Item item = maxHeap.poll();
                char c = item.c;
                int freq = item.freq;
                while (freq != 0) {
                    sb.append(c);
                    freq--;
                }
            }
            return sb.toString();
        }
        
        private class Item {
            char c;
            int freq;
            Item(char c, int freq) {
                this.c = c;
                this.freq = freq;
            }
        }
    }
    

Log in to reply
 

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