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.

 1 public class Solution {
 2     public String frequencySort(String s) {
 3         Map<Character, Integer> map = new HashMap<>();
 4         for (char c : s.toCharArray()) {
 5             if (map.containsKey(c)) {
 6                 map.put(c, map.get(c) + 1);
 7             } else {
 8                 map.put(c, 1);
 9             }
10         }
11         List<Character> [] bucket = new List[s.length() + 1];
12         for (char key : map.keySet()) {
13             int frequency = map.get(key);
14             if (bucket[frequency] == null) {
15                 bucket[frequency] = new ArrayList<>();
16             }
17             bucket[frequency].add(key);
18         }
19         StringBuilder sb = new StringBuilder();
20         for (int pos = bucket.length - 1; pos >=0; pos--) {
21             if (bucket[pos] != null) {
22                 for (char num : bucket[pos]) {
23                     for (int i = 0; i < map.get(num); i++) {
24                         sb.append(num);
25                     }
26                 }
27             }
28         }
29         return sb.toString();
30     }
31 }

 1 public class Solution {
 2     public String frequencySort(String s) {
 3         PriorityQueue<WrapperChar> maxheap = new PriorityQueue(1, new Comparator<WrapperChar>() {
 4             public int compare(WrapperChar w1, WrapperChar w2) {
 5                 return w2.count - w1.count;
 6             }
 7         });
 8         HashMap<Character, WrapperChar> map = new HashMap<Character, WrapperChar>();
 9         for (int i=0; i<s.length(); i++) {
10             char c = s.charAt(i);
11             if (!map.containsKey(c)) map.put(c, new WrapperChar(c, 1));
12             else {
13                 int newCount = map.get(c).count + 1;
14                 map.put(c, new WrapperChar(c, newCount));
15             }
16         }
17         for (char c : map.keySet()) maxheap.offer(map.get(c));
18         StringBuilder res = new StringBuilder();
19         while (!maxheap.isEmpty()) {
20             WrapperChar wChar = maxheap.poll();
21             for (int i=0; i<wChar.count; i++) {
22                 res.append(wChar.c);
23             }
24         }
25         return res.toString();
26     }
27     
28     public class WrapperChar {
29         char c;
30         int count;
31         public WrapperChar(char ch, int num) {
32             this.c = ch;
33             this.count = num;
34         }
35     }
36 }