Formatted question description: https://leetcode.ca/all/451.html

# 451. Sort Characters By Frequency (Medium)

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.


Related Topics:
Hash Table, Heap

Similar Questions:

## Solution 1.

// OJ: https://leetcode.com/problems/sort-characters-by-frequency/

// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
string frequencySort(string s) {
int cnt = {};
for (char c : s) cnt[c]++;
sort(s.begin(), s.end(), [&](char a, char b) {
return cnt[a] == cnt[b] ? a > b : cnt[a] > cnt[b];
});
return s;
}
};


## Solution 2.

// OJ: https://leetcode.com/problems/sort-characters-by-frequency/

// Time: O(N)
// Space: O(1)
class Solution {
public:
string frequencySort(string s) {
vector<char> v;
int cnt = {};
for (char c : s) {
if (cnt[c]++ == 0) v.push_back(c);
}
sort(v.begin(), v.end(), [&](char a, char b) { return cnt[a] > cnt[b]; });
string ans;
for (char c : v) {
for (int i = 0; i < cnt[c]; ++i) ans.push_back(c);
}
return ans;
}
};


Java

class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
char[] array = s.toCharArray();
for (char c : array) {
int count = map.getOrDefault(c, 0);
count++;
map.put(c, count);
}
List<CharacterCount> list = new ArrayList<CharacterCount>();
Set<Character> keySet = map.keySet();
for (char c : keySet) {
int count = map.getOrDefault(c, 0);
}
Collections.sort(list);
StringBuffer sortedSB = new StringBuffer();
for (CharacterCount characterCount : list) {
char character = characterCount.character;
int count = characterCount.count;
for (int i = 0; i < count; i++)
sortedSB.append(character);
}
return sortedSB.toString();
}
}

class CharacterCount implements Comparable<CharacterCount> {
char character;
int count;

public CharacterCount(char character, int count) {
this.character = character;
this.count = count;
}

public int compareTo(CharacterCount characterCount2) {
return characterCount2.count - this.count;
}
}