Abstract / Summary

Given a string, rearrange its characters so they are ordered by how often each character appears.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 75% (1+ million submissions).

Typical patterns to solve this problem:

• Bucket Sort
• Counting
• Hash Table
• Heap (Priority Queue)
• Sorting
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method frequencySort. The method receives a string s and returns a new string where characters are ordered by descending frequency of occurrence. Characters that share the same frequency appear together, preserving the order in which they were first encountered in the input. The algorithm relies on Python’s defaultdict to simplify counting and grouping, and it uses a bucket-style traversal to avoid an explicit sort of the frequency map.

Counting Character Frequencies

The first logical block builds a histogram of how many times each character appears. By using defaultdict(int), the code eliminates the need for explicit existence checks before incrementing a count.

freq = defaultdict(int)
for c in s:
    freq[c] += 1

Each iteration updates the count for the current character c. This step runs in linear time relative to the length of s and leverages the constant-time dictionary operations provided by CPython.

Grouping Characters by Frequency

After the histogram is ready, the code creates a second mapping that groups characters sharing the same frequency. The key of this mapping is the frequency, and the value is a concatenated string of characters that occur that many times.

all = defaultdict(str)
for f in freq:
    all[freq[f]] += f

Because defaultdict(str) initializes missing keys with an empty string, the += operator safely appends each character to the appropriate bucket. This grouping step prepares the data for a descending traversal without requiring a sort of the frequency keys.

Determining the Highest Frequency

To know where to start the descending walk, the algorithm extracts the maximum frequency present in the input.

high = max(freq.values())

The max function scans the values of the freq dictionary once, yielding the largest count. This value defines the upper bound for the subsequent loop.

Building the Result String

The final phase iterates from the highest frequency down to one, appending each character the appropriate number of times. The inner loop walks through the string stored in the bucket for the current frequency, and the multiplication j * i repeats the character j exactly i times.

result = ""
for i in range(high + 1, 0, -1):
    for j in all[i]:
        result += j * i

By iterating in descending order, the method guarantees that higher-frequency characters appear earlier in the output. The use of string multiplication (j * i) efficiently creates the repeated segment for each character without an explicit inner loop.

Edge Cases Handled

When the input contains characters that all appear the same number of times, the grouping step places them together in a single bucket. The subsequent descending traversal then emits them in the order they were first seen, because the bucket string preserves insertion order.

If the string consists of a single unique character repeated many times, the histogram contains one entry, the bucket for that frequency holds that character, and the result is simply the original string reproduced.

For inputs where some characters appear only once, the algorithm still creates a bucket for frequency 1. The descending loop reaches this bucket last, ensuring that low-frequency characters are placed at the end of the output.

The method also works correctly for strings containing a mixture of alphabetic, numeric, and symbolic characters, as the dictionary keys are generic hashable objects (single-character strings).

Performance Optimizations Observed

The code avoids an explicit sort of the frequency dictionary, which would be O(k log k) for k distinct characters. Instead, it employs a bucket-style approach: frequencies become keys in a second dictionary, and the algorithm walks the buckets from the maximum frequency down to one. This technique reduces the ordering step to linear time with respect to the range of frequencies, which is bounded by the length of the input string.

Using defaultdict for both the histogram and the bucket map eliminates conditional checks for key existence, streamlining the inner loops and reducing Python bytecode overhead.

String multiplication (j * i) leverages the highly optimized C implementation of the * operator for strings, producing repeated characters in a single operation rather than concatenating in a loop.

Finally, the result string is built by repeated concatenation. While Python strings are immutable, the concatenations occur in a pattern where each addition appends a relatively large chunk (the entire repeated segment for a character). This reduces the number of intermediate objects compared to appending single characters repeatedly, mitigating the typical performance penalty of naive string concatenation.

Imagine you have a big box of colorful building blocks and you want to organize them. This code starts by looking at every block in the box to see how many times each color shows up. It keeps a note of these counts, like writing down that there are five red blocks and two blue ones.

After knowing how many of each color there are, the code creates a new way to pick them up. It groups the blocks by their popularity, putting all the colors that appear the same number of times together.

Finally, the code goes through these groups, starting with the group that appeared the most often and working down to the ones that show up just once. As it visits each group, it grabs every block in that group and adds them to a new line in the exact amount they appeared. By the time it finishes, all the same colors are sitting together in a row, sorted by how often they appeared in the original box.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java									TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			Rust			Go		PHP	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	BigEggStudy					C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	DimitrisJim										C
	everthis				JS
	fartem							Ruby
	fengvyi	C++
	fpdjsns	C++
	halfrost									Go
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	pruthvikp		Python
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	yuanliu666								Kotlin
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
pruthvikp	Python
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
yuanliu666	Kotlin
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality