[Leetcode]Sort Characters By Frequency

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.

Analysis:

The idea is simple: count the frequency of each character, and then sort the characters by frequency and out put the characters. We can use a two dimension array for the easy counting and sorting. 

public String frequencySort(String s) {
        int[][] count = new int[256][2];
        
        for(char c: s.toCharArray()) {
            count[c][0] = c;
            count[c][1]++;
        }
        
        Arrays.sort(count, new Comparator<int[]>() {
           public int compare(int[] a, int[] b) {
               return a[1] == b[1] ? 0 : (a[1] < b[1] ? 1 : -1);
           } 
        });
        
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<256; i++) {
            if (count[i][1] > 0) {
                for(int j=0; j<count[i][1]; j++) {
                    sb.append((char)count[i][0]);
                }
            }
        }
        
        return sb.toString();
    }