LeetCode [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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: string frequencySort(string s) { map<char, int> mp; for(auto c:s){ mp[c]++; } priority_queue<pair<int, char>> pq; for(auto h:mp){ pq.push(make_pair(h.second, h.first)); } string r; while(!pq.empty()){ r.append(pq.top().first, pq.top().second); pq.pop(); } return r; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

//Java, Bucket Sort class Solution { public String frequencySort(String s) { int n = s.length(); char[] chars = s.toCharArray(); Map<Character, Integer> freq = new HashMap<>(); for(char c : chars){ freq.put(c, freq.getOrDefault(c, 0)+1); } List<Character>[] buckets = new List[n+1]; for(Map.Entry<Character, Integer> e : freq.entrySet()){ char c = e.getKey(); int cnt = e.getValue(); if(buckets[cnt]==null){ buckets[cnt] = new ArrayList<>(); } buckets[cnt].add(c); } StringBuilder sb = new StringBuilder(); for(int i=n; i>0; --i){ if(buckets[i]==null) continue; for(char c : buckets[i]){ for(int j=0; j<freq.get(c); ++j){ sb.append(c); } } } return sb.toString(); } }