Sort Characters By Frequency

LeetCode Q 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

Code:

public String frequencySort(String s) {
	if (s == null || s == "")
		return "";
	
	Map<Character, Integer> map = new HashMap<>();
	for (char ch: s.toCharArray()) 
		map.put(ch, map.getOrDefault(ch, 0) + 1);
	
	List<Character>[] buckets = new List[s.length() + 1];
	for (char ch: map.keySet()) {
		int freq = map.get(ch);
		if (buckets[freq] == null) buckets[freq] = new ArrayList<>();
		buckets[freq].add(ch);
	}
	
	StringBuilder res = new StringBuilder();
	for (int i = buckets.length - 1; i >= 0; i--) {
		if (buckets[i] == null) continue;
		for (char ch: buckets[i])
			for (int num = 0; num < i; num++)
				res.append(ch);
	}
	
	return res.toString();
}