Java: Sort Characters By Frequency

Thought Process

The core approach involves counting character frequencies and then sorting them in descending order. First, we use a hash map to count each character's frequency. Then, we use a max heap to efficiently retrieve characters with highest frequencies. Finally, we construct the result string by appending characters according to their frequencies from the heap. 

class Solution {
    
    public String frequencySort(String s) {
        
        Map<Character,Integer> mp = new HashMap<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->Integer.compare(b[1],a[1]));
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++){

            char ch = s.charAt(i);
            mp.put(ch,mp.getOrDefault(ch,0)+1);
        }

        for(Map.Entry<Character,Integer> entity : mp.entrySet()){

            int key = entity.getKey();
            int val = entity.getValue();

            pq.offer(new int[]{key,val});
        }
        while(!pq.isEmpty()){

            int[] arr = pq.poll();
            char val = (char)arr[0];
            int freq = arr[1];
            for(int i=0;i<freq;i++)
                sb.append(val);
        }
        return sb.toString();
    }
}

Code Complexity

Time Complexity: O(n log n)

Building the frequency map takes O(n) time, and heap operations take O(n log n) in the worst case.

Space Complexity: O(n)

We use extra space for the frequency map and priority queue, both proportional to the input size.

Code copied!