How do you solve Sort Characters By Frequency?

Use a hash map to count the frequency of each character in a single pass over the string. Then, sort the map entries by frequency in descending order. Finally, build the result string by repeating each character according to its frequency. This approach achieves O(n log k) time complexity, where k is the number of unique characters, and O(k) space complexity.

What pattern does Sort Characters By Frequency use?

The Pattern: Hash Maps (Frequency Counting and Sorting) The Heuristic: When a problem requires grouping elements by frequency and then ordering them, use a hash map to count frequencies followed by sorting the entries by their counts to efficiently reconstruct the desired output.

Sort Characters By Frequency — Hash Maps

Q: What is the time complexity of Sort Characters By Frequency?

O(n log k). Counting frequencies takes O(n) time, where n is the length of the string. Sorting the frequency map entries takes O(k log k), where k is the number of unique characters. Since k ≤ n, the overall complexity is O(n log k).

Problem

Given a string s, return a string where the characters are sorted in descending order based on their frequency of occurrence.

1 ≤ s.length ≤ 5 * 10⁵
s consists of ASCII characters.

Example

Input: s = "tree"

Output: "eert"

The character 'e' appears twice, while 't' and 'r' appear once each. Sorting by frequency places 'e' first, resulting in "eert" or "eetr". The algorithm counts frequencies using a hash map, then sorts characters by their counts in descending order. It then reconstructs the string by repeating each character according to its frequency.

Approach

Straightforward Solution

A naive approach would repeatedly scan the string to count frequencies for each character, resulting in O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

The problem requires grouping characters by frequency and then ordering these groups from highest to lowest frequency. The fundamental truth is that frequency counting is naturally suited to hash maps, which provide O(1) average-time insertion and lookup.

Path to Optimal

Preview

The key recognition signals are 'frequency of characters', 'sort by frequency', and 'return string sorted by frequency'. These indicate the Hash Maps pattern because counting frequencies requires a data structure with fast insertion and lookup…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a hash map to count the frequency of each character in a single pass over the string. Then, sort the map entries by frequency in descending order…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log k)

Counting frequencies takes O(n) time, where n is the length of the string. Sorting the frequency map entries takes O(k log k), where k is the number of unique characters. Since k ≤ n, the overall complexity is O(n log k).

Space

O(k)

The hash map stores frequencies for each unique character, requiring O(k) auxiliary space, where k is the number of unique characters in the string.

Solution

Python

1class Solution:
2    def frequencySort(self, s: str) -> str:
3
4        freq = {}
5
6        for ch in s:
7            freq[ch] = freq.get(ch, 0) + 1
8
9        result = []
10
11        for ch, count in sorted(freq.items(), key=lambda x: x[1], reverse=True):
12            result.append(ch * count)
13
14        return "".join(result)

Step-by-Step Solution

1

Count Frequencies of Each Character Using a Hash Map

4freq = {}
6for ch in s:
7    freq[ch] = freq.get(ch, 0) + 1

Objective

To build a frequency map that records how many times each character appears in the input string.

Key Insight

A hash map provides O(1) average-time insertion and lookup, making it ideal for counting frequencies in a single pass. By incrementing the count for each character as it is encountered, the algorithm efficiently aggregates frequency data without redundant scans.

Interview Quick-Check

Core Logic

Use a hash map to count occurrences of each character in one pass, enabling efficient frequency aggregation.

Common Pitfalls & Bugs

Forgetting to initialize counts or using a data structure with slower lookups (like a list for all ASCII chars) can degrade performance.

2

Sort Characters by Frequency in Descending Order

To order the characters based on their frequency counts from highest to lowest.

3

Build the Result String by Repeating Characters According to Frequency

To construct the final output string by concatenating each character repeated by its frequency count.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 11 Critical

for ch, count in sorted(freq.items(), key=lambda x: x[1], reverse=True):

Sort the frequency dictionary items by frequency in descending order.

Sorting by frequency ensures that characters with higher counts appear first in the output, which is the core requirement of the problem.

Line 7 Critical

freq[ch] = freq.get(ch, 0) + 1

Increment the frequency count for the current character in the dictionary.

Using `get` with a default of 0 ensures that characters not yet seen are initialized properly, preventing key errors and enabling correct counting.

Line 14 Critical

return "".join(result)

Join all parts in the result list into a single string and return it.

Joining the list of repeated characters produces the final output string efficiently in O(n) time, where n is the length of the input string.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why is sorting the frequency map entries by their counts necessary instead of just iterating over the map?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Sort Characters By Frequency from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sort Characters By Frequency drill

or drill a free problem

1	`class Solution:`
2	`def frequencySort(self, s: str) -> str:`
3
4	`freq = {}`
5
6	`for ch in s:`
7	`freq[ch] = freq.get(ch, 0) + 1`
8
9	`result = []`
10
11	`for ch, count in sorted(freq.items(), key=lambda x: x[1], reverse=True):`
12	`result.append(ch * count)`
13
14	`return "".join(result)`