Algorithm
Problem Name: 451. Sort Characters By Frequency
Problem Link: https://leetcode.com/problems/sort-characters-by-frequency/
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.
Example 1:
Input: s = "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: s = "cccaaa" Output: "aaaccc" Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers. Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input: s = "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.
Constraints:
1 <= s.length <= 5 * 105sconsists of uppercase and lowercase English letters and digits.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string frequencySort(string s) {
string res = "";
unordered_map < char, int>m;
for(auto c: s) m[c]++;
auto comp = [](pair < int, char>& a, pair<int, char>& b){ return a.first < b.first; };
priority_queue < pair<int, char>, vector<pair<int, char>>, decltype(comp)>pq(comp);
for(auto x: m) pq.push({x.second, x.first});
while(!pq.empty()){
auto p = pq.top();
pq.pop();
while(p.first--) res += p.second;
}
return res;
}
};
Input
s = "tree"
Output
"eert"
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
private static final String ALL_LETTERS =
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
public String frequencySort(String s) {
Map < Character, Integer> map = new HashMap<>();
int maxFrequency = 0;
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
maxFrequency = Math.max(maxFrequency, map.get(c));
}
List < Character>[] frequencyToChar = new List[maxFrequency + 1];
for (char c : map.keySet()) {
if (frequencyToChar[map.get(c)] == null) {
frequencyToChar[map.get(c)] = new ArrayList<>();
}
frequencyToChar[map.get(c)].add(c);
}
StringBuilder sb = new StringBuilder();
for (int i = maxFrequency; i > 0; i--) {
List < Character> characters = frequencyToChar[i] == null ?
new ArrayList<>() : frequencyToChar[i];
for (char c : characters) {
for (int j = 0; j < i; j++) {
sb.append(c);
}
}
}
return sb.toString();
}
}
Input
s = "tree"
Output
"eert"
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const frequencySort = function(s) {
const charMap = {};
for (let i = 0; i < s.length; i++) {
const index = s.charAt(i);
charMap[index] = (charMap[index] || 0) + 1;
}
return Object.entries(charMap)
.sort((a, b) => {
return b[1] - a[1];
})
.map(x => {
return x[0].repeat(x[1]);
})
.join("");
};
Input
s = "cccaaa"
Output
"aaaccc"
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def frequencySort(self, s: str) -> str:
cnt = collections.Counter(s)
res = ''
for k, v in sorted(cnt.items(), key = lambda x: -cnt[x[0]]):
res += k * v
return res
Input
s = "cccaaa"
Output
"aaaccc"
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LeetCode
{
public class _0451_SortCharactersByFrequency
{
public string FrequencySort(string s)
{
if (string.IsNullOrWhiteSpace(s)) return s;
var counts = new Dictionary < char, int>();
foreach (var ch in s)
{
if (!counts.ContainsKey(ch))
counts.Add(ch, 1);
else
counts[ch]++;
}
var maxCount = counts.Values.Max();
var buckets = new List < IList());
foreach (var ch in counts.Keys)
buckets[counts[ch]].Add(ch);
var sb = new StringBuilder();
for (int i = maxCount; i >= 1; i--)
foreach (var ch in buckets[i])
sb.Append(ch, i);
return sb.ToString();
}
}
}
Input
s = "Aabb"
Output
"bbAa"