Sort Characters By Frequency

Question

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.

LeetCodeleetcode.com/problems/sort-characters-by-frequency

Solution

/*
@param: String
@return: String
Algorithm: 这题同https://leetcode.com/problems/top-k-frequent-elements/
*/
public String frequencySort(String s) {
    if (s.length() <= 2) {
        return s;
    }
    
    Map<Character, Integer> map = new HashMap<>();
    PriorityQueue<Character> heap = new PriorityQueue<>( (o1,o2) -> map.get(o2) - map.get(o1));
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        map.put(c, map.getOrDefault(c, 0)+1);            
    }
    
    for (char c : map.keySet()) {
        heap.offer(c);
    }
    
    StringBuilder res = new StringBuilder();
    
    while (!heap.isEmpty()) {
        char c = heap.poll();
        for (int i = 0; i < map.get(c); i++) {
            res.append(c);
        }            
    }
    return res.toString();
}