451 Sort Characters By Frequency

451. Sort Characters By Frequency

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

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.

2. Implementation

(1) Bucket Sort

class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }

        int[] map = new int[256];

        for (char c : s.toCharArray()) {
            map[c]++;
        }

        List<Character> bucket[] = new List[s.length() + 1];

        for (char key = 0; key < map.length; key++) {
            if (map[key] != 0) {
                int freq = map[key];

                if (bucket[freq] == null) {
                    bucket[freq] = new ArrayList<>();
                }
                bucket[freq].add(key);
            }
        }

        StringBuilder res = new StringBuilder();
        for (int i = bucket.length - 1; i >= 0; i--) {
            if (bucket[i] != null) {
                for (char c : bucket[i]) {
                    while (map[c]-- > 0) {
                        res.append(c);
                    }
                }
            }
        }
        return res.toString();
    }
}

(2) Heap

class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        int[] map = new int[256];

        for (char c : s.toCharArray()) {
            ++map[c];
        }

        PriorityQueue<CharInfo> maxHeap = new PriorityQueue<>();

        for (int i = 0; i < 256; i++) {
            if (map[i] != 0) {
                maxHeap.add(new CharInfo((char)i, map[i]));
            }
        }

        StringBuilder res = new StringBuilder();

        while (!maxHeap.isEmpty()) {
            CharInfo curChar = maxHeap.remove();

            while (--curChar.freq >= 0) {
                res.append(curChar.val);
            }
        }
        return res.toString();
    }

    class CharInfo implements Comparable<CharInfo> {
        char val;
        int freq;

        public CharInfo(char val, int freq) {
            this.val = val;
            this.freq = freq;
        }

        public int compareTo(CharInfo that) {
            return that.freq - this.freq;
        }
    }
}

3. Time & Space Complexity

Bucket Sort: 时间复杂度O(n), 空间复杂度O(n)

Heap: 时间复杂度O(n), 空间复杂度O(n)