313. Sort Characters By Frequency
Medium
Frequency Map and Buckets
Hashing
Problem
Given a string s, sort its characters in decreasing order based on their frequency and return the resulting string. Characters with the same frequency may appear in any relative order, but identical characters must remain grouped together.
Examples
Example 1
Input: "tree"
Output: "eetr"
Example 2
Input: "cccaaa"
Output: "cccaaa"
Example 3
Input: "Aabb"
Output: "bbAa"
Constraints
� 1 <= s.length <= 500000
� s consists of uppercase letters, lowercase letters and digits.
Hints
?? Count the frequency of every character first.
?? A max heap can repeatedly return the most frequent character.
?? Frequency cannot exceed s.length, so buckets indexed by frequency are another option.
Expected Complexity
Time: O(n) with bucket sorting
Space: O(n)
Follow-up
Can you solve it in O(n) time using bucket sorting?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
"tree"Expected
"eetr"