Sort Letters by Frequency
Problem
Rearrange the characters of a string so that equal characters sit together and the groups appear from most frequent to least frequent. When two characters appear equally often, the one whose first appearance in the input is earlier goes first. Return the rearranged string, and do it without a comparison sort over the characters.
Examples
Input: text = "banana"
Output: "aaannb"
Why: a appears 3 times, n twice and b onceInput: text = "mississippi"
Output: "iiiissssppm"
Why: i and s both appear 4 times, and i shows up first in the inputInput: text = ""
Output: ""
Why: edge case, nothing to rearrangeHints
0 / 3
Counting each character is the easy part. The question is how to order the counts without sorting them.
A count can never be larger than the length of the string, so the counts themselves can serve as indexes into a list of buckets.
Count characters in a dictionary, which keeps them in first-appearance order. Drop each character into bucket number count, then walk the buckets from the highest index down, writing each character count times.
Solution
A count is a whole number between 1 and the length of the string, so a list of buckets indexed by count sorts the characters in linear time. Python dictionaries keep insertion order, so the counter lists characters by first appearance, and filling the buckets in that order settles every tie. Walking the buckets from the top writes the most frequent group first. Time is O(n), and space is O(n) for the buckets and the output.
from collections import Counter
def by_frequency(text):
counts = Counter(text) # keys in first-appearance order
buckets = [[] for _ in range(len(text) + 1)]
for ch, c in counts.items():
buckets[c].append(ch) # ties stay in first-appearance order
parts = []
for c in range(len(text), 0, -1): # most frequent bucket first
for ch in buckets[c]:
parts.append(ch * c)
return "".join(parts)
print(by_frequency("banana")) # -> aaannb
print(by_frequency("mississippi")) # -> iiiissssppm
print(by_frequency("")) # -> (empty string)Stuck on the idea rather than the code? Top K Without a Heap covers it.