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.</pre>

Solution

HashMap + PriorityQueue, time O(nlogn), space O(n)

注意边界条件处理。如果s为空，构建PriorityQueue如果指定size会抛RuntimeException。或者实例化时不指定size也可以。

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> charToFrequency = new HashMap<>();
        for (int i = 0; i < s.length(); ++i) {
            charToFrequency.put(s.charAt(i)
                                , charToFrequency.getOrDefault(s.charAt(i), 0) + 1);
        }

        PriorityQueue<Map.Entry<Character, Integer>> queue
            = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>() {
                public int compare(Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) {
                    return b.getValue() - a.getValue();
                }
            });
        
        queue.addAll(charToFrequency.entrySet());   // elegent!
        
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            Map.Entry<Character, Integer> entry = queue.poll();
            for (int i = 0; i < entry.getValue(); ++i) {
                sb.append(entry.getKey());
            }
        }
        
        return sb.toString();
    }
}

HashMap + Bucket sort, time O(n), space O(n)

利用一个List<Charater>[s.length() + 1]的bucket辅助。