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.

Solution

public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(char c: s.toCharArray()) {
            if(!map.containsKey(c)) map.put(c, 0);
            map.put(c, map.get(c) + 1);
        }

        List<Map.Entry<Character, Integer>> list = new ArrayList<Map.Entry<Character, Integer>>(map.size());
        list.addAll(map.entrySet());

        Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
            public int compare(Map.Entry<Character, Integer> entry1, Map.Entry<Character, Integer> entry2) {
                return entry2.getValue() - entry1.getValue(); 
            }
        });

        StringBuilder sb = new StringBuilder();
        for(Map.Entry<Character, Integer> entry: list) {
            char c = entry.getKey();
            int repeat = entry.getValue();
            for(int i = 0; i < repeat; i++) {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}