451.md

451. Sort Characters by Frequency

Description

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Thinking Process

1. Iterate the string, build a map of how many times each characters have appeared
2. Put the all map entries into a heap
3. Take out heap elements one by one and recreate the string

Code

public class Solution {
    public String frequencySort(String s) {
        StringBuilder sb = new StringBuilder();
        Map<Character, Integer> map = new HashMap<>();
    
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){
                map.put(c, map.get(c) + 1);
            }else{
                map.put(c, 1);
            }
        }
        
        PriorityQueue<Entry> heap = new PriorityQueue<>();
        for(Character key:map.keySet()){
            Entry e = new Entry(key, map.get(key));
            heap.add(e);
        }
        
        while(!heap.isEmpty()){
            Entry e = heap.poll();
            for(int i = 0; i < e.feq; i++){
                sb.append(e.key);
            }
        }
        
        return sb.reverse().toString();
    }
    
    class Entry implements Comparable<Entry>{
        char key;
        int feq;
        
        Entry(char key, int feq){
            this.key = key;
            this.feq = feq;
        }
        @Override
        public int compareTo(Entry other) {
            if(feq > other.feq){
                return 1;
            }
            else if(feq == other.feq){
                return 0;
            }
            else{
                return -1;
            }
        }
    }
}

Complexity

1. Time complexity is O(nlogn) as adding everyting to heap takes O(nlogn) time
2. Space complexity is O(n)