451. 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.

Solution:

This is a bucket sort problem.

We first count the frequency of each character and maintains a max frequency.

The size of bucket array is the max + 1.

bucket[i] denotes the character(s) who has frequency of i.

We can go through the frequency map and insert each character to the corresponding bucket.

Finally, we start from the max frequency and put all characters from non-empty buckets to the result string.

The time complexity is O(n) and the space complexity is O(n).



Code:

public class Solution {
    public String frequencySort(String s) {
        int[] map = new int[256];
        int max = 0;
        for (char c : s.toCharArray()) {
            map[c]++;
            max = Math.max(max, map[c]);
        }
        String[] bucket = new String[max + 1];
        for (int i = 0; i < 256; i++) {
            String str = bucket[map[i]];
            if (map[i] > 0) {
                bucket[map[i]] = str == null ? "" + (char) i : str + (char) i;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = max; i >= 0; i--) {
            if (bucket[i] != null) {
                for (char c : bucket[i].toCharArray()) {
                    for (int j = 0; j < i; j++) {
                        sb.append(c);
                    }
                }
            }
        }
        return sb.toString();
    }
}