Given a string s, reorder its characters so that they appear in decreasing order of how often they occur. All copies of a character must sit together. Characters with the same frequency may appear in any order. Uppercase and lowercase letters are different characters.
- 1 <= s.length <= 5 * 10^5
- s has uppercase and lowercase English letters and digits
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Counting and then sorting the distinct characters by frequency is O(n + m log m), already fine here. A neat linear alternative is bucket sort: a frequency is an integer from 1 to n, so put each character into bucket[freq]. Reading the buckets from the highest frequency down, and writing each character freq times, builds the answer in O(n) with every character grouped.
Algorithm
- Count how often each character appears.
- Create
n + 1empty buckets and put each character intobucket[count]. - Walk
ffromndown to 1, and for each character inbucket[f]append itftimes. - Return the built string.
O(n)Space: O(n)class Solution: def frequencySort(self, s: str) -> str: n = len(s) count = Counter(s) bucket = [[] for _ in range(n + 1)] # bucket[f] = characters seen f times for ch, f in count.items(): bucket[f].append(ch) out = [] for f in range(n, 0, -1): for ch in bucket[f]: out.append(ch * f) return "".join(out)