Sort characters in a string by decreasing frequency.
Problem Statement
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. Characters with equal frequency should be ordered deterministically.
Examples
Input: s = "tree"
Output: "eert"
Explanation: Combining the input according to Sort Characters by Frequency logic yields "eert".
Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Combining the input according to Sort Characters by Frequency logic yields "aaaccc".
Complexity
Time Complexity: O(N + K log K)
Space Complexity: O(N)
Hints
š” Hint 1:
Count the frequency of each character using a Hash Map.
š” Hint 2:
Convert the map into an array of [char, count] pairs and sort descending by frequency.
š” Hint 3:
Reconstruct the string by repeating each character count times and concatenating.
Editorial & Approach
Problem Overview & Intuition
Count character frequencies with a Map in O(N). Sort unique characters by frequency in O(K log K) where K <= 62 (alphanumeric). Constructing the result string by repeating characters takes O(N) time.
Step-by-Step Approach
- Count frequencies using
map = new Map(). - Convert to entries array and sort descending:
sort((a, b) => b[1] - a[1]). - Map each entry to
char.repeat(count)and join. - Return reconstructed string.
Optimal Implementation (JavaScript)
function frequencySort(s) {
const map = new Map();
for (let c of s) {
map.set(c, (map.get(c) || 0) + 1);
}
return [...map.entries()]
.sort((a, b) => b[1] - a[1])
.map(([c, count]) => c.repeat(count))
.join('');
}Complexity Analysis
Time Complexity
O(N + K log K) where K is number of unique characters.
Space Complexity
O(N) for map and output string.
Edge Cases & Corner Traps Handled
- Case sensitivity: "c" and "C" treated as distinct characters.
- All characters identical: returns string unchanged.
- Single character string.