Skip to main content
Talentd

Sort Characters By Frequency - Solution & Explanation

MediumHash TableStringSortingHeap (Priority Queue)18 min readAsked at: Amazon, Microsoft, Meta +13
Practice this problem

Problem Statement

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

 

Example 1:

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

 

Constraints:

  • 1 <= s.length <= 5 * 105
  • s consists of uppercase and lowercase English letters and digits.

Approach Overview

Problem Overview: Given a string s, reorder its characters so that characters with higher frequency appear first. If two characters have the same frequency, their relative order does not matter. The goal is to efficiently count occurrences and rebuild the string sorted by frequency.

Approach 1: HashMap + Sorting (O(n log k) time, O(n) space)

Count the frequency of every character using a HashMap. Once frequencies are known, convert the map entries into a list and sort them by frequency in descending order. After sorting, iterate through the pairs and append each character frequency times to the result string. The sorting step dominates the runtime with O(k log k), where k is the number of unique characters (at most n). This approach is simple and readable, making it a strong default when working with hash tables and sorting.

The key insight is separating the problem into two phases: counting and ordering. Counting is linear using a hash lookup per character, and sorting ensures the highest frequency characters appear first. Many implementations also replace sorting with a priority queue (max heap), which repeatedly extracts the highest-frequency character. That version has the same O(n log k) complexity but uses a heap instead of sorting.

Approach 2: Counting + Bucket Sort (O(n) time, O(n) space)

A faster approach avoids comparison-based sorting entirely. First compute character frequencies with a map or fixed-size array. Then create a bucket array where index i stores all characters that appear exactly i times. Because the maximum frequency is at most n, the bucket array size is n + 1. Iterate the buckets from highest frequency down to 1 and append each character i times to the result.

This works because frequencies are integers within a limited range. Instead of sorting characters by frequency, you directly place them into frequency-indexed buckets. Building the frequency map takes O(n), distributing characters into buckets takes O(k), and constructing the result string takes O(n). The entire process runs in linear time, which makes this the optimal solution for large inputs and a good demonstration of bucket sort principles.

Recommended for interviews: Start with the HashMap + sorting approach because it clearly shows the frequency-count pattern used in many string problems. After that, mention the bucket sort optimization. Interviewers typically expect candidates to recognize that sorting by frequency can be replaced with buckets for an O(n) solution.

Approach 1: Using HashMap and Sorting

This approach involves using a hash map to count the frequency of each character, followed by sorting the characters by frequency in descending order. Here's how the approach works step-by-step:

  1. Use a hash map (or a dictionary) to store the frequency of each character in the string.
  2. Convert the hash map to a list of tuples (or a priority queue), where each tuple contains a character and its frequency.
  3. Sort this list of tuples primarily by frequency in descending order. If two characters have the same frequency, the order can be arbitrary since any valid ordering is acceptable.
  4. Construct the result string by repeating each character in the sorted list according to its frequency.

In this Python solution, the collections.Counter class is used to create a frequency map of the characters. We then sort the items of this map based on frequency and concatenate them to form the result string.

Code

PythonC++JavaC#JavaScriptC

Python

C++

Java

C#

JavaScript

C

Complexity

Time Complexity: O(n log n), where n is the length of the string due to sorting.
Space Complexity: O(n), for the frequency map storage.

Try this approach in the editor →

Approach 2: Using Counting Sort and Bucket Sort

This approach leverages the Bucket Sort technique where we'll map frequencies to characters directly. This is especially efficient when the range of possible frequencies is low compared to the number of characters.

  1. Count the frequency of each character using a fixed-size array (as we are dealing with ASCII).
  2. Create an array of buckets, where each bucket at index i stores characters appearing i times.
  3. Build the output from the highest frequency bucket to the lowest.

In this Python solution, we first use a defaultdict to obtain the frequency table. After establishing frequency buckets, we build the result by iterating over frequencies in descending order.

Code

PythonC++JavaC#JavaScriptC

Python

C++

Java

C#

JavaScript

C

Complexity

Time Complexity: O(n), since we distribute the frequencies and read back them in linear time.
Space Complexity: O(n), for the result string and bucket storage.

Try this approach in the editor →

Approach 3: Hash Table + Sorting

We use a hash table cnt to count the occurrences of each character in the string s. Then, we sort the key-value pairs in cnt in descending order by the number of occurrences. Finally, we concatenate the characters according to the sorted order.

The time complexity is O(n + k times log k), and the space complexity is O(n + k), where n is the length of the string s, and k is the number of distinct characters.

Code

PythonJavaC++GoTypeScriptRustPHP

Python

Java

C++

Go

TypeScript

Rust

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using HashMap and Sorting

Time Complexity: O(n log n), where n is the length of the string due to sorting.
Space Complexity: O(n), for the frequency map storage.

Using Counting Sort and Bucket Sort

Time Complexity: O(n), since we distribute the frequencies and read back them in linear time.
Space Complexity: O(n), for the result string and bucket storage.

Hash Table + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap + SortingO(n log k)O(n)General solution that is simple to implement and easy to explain in interviews
HashMap + Max HeapO(n log k)O(n)Useful when repeatedly extracting highest frequency elements
Counting + Bucket SortO(n)O(n)Best performance when frequencies are bounded and linear-time solution is desired

Video Solution

Sort Characters By Frequency | Leetcode #451 • Techdose • 63,148 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sort Characters By Frequency easy or hard?
Sort Characters By Frequency is generally considered a medium-level problem. The core challenge is recognizing the frequency-count pattern and selecting the right structure to order characters efficiently, such as sorting, a heap, or bucket sort.
Sort Characters By Frequency Python/Java solution
In Python or Java, the common solution counts characters with a dictionary or HashMap, then sorts the entries by frequency in descending order and builds the output string. Python often uses collections.Counter with sorted, while Java uses HashMap with a custom comparator or priority queue.
How to solve Sort Characters By Frequency in O(n)?
Use a frequency map to count occurrences of each character. Create an array of buckets where index i stores characters that appear i times. Iterate from the highest frequency bucket down to 1 and append characters accordingly. Since each character is processed a constant number of times, the overall complexity is O(n).
What is the best approach for Sort Characters By Frequency?
The most practical solution uses a HashMap to count character frequencies and then sorts the characters by frequency in descending order. This runs in O(n log k) time where k is the number of unique characters. An even faster approach uses bucket sort to achieve O(n) time by grouping characters by their frequency.
Is Sort Characters By Frequency asked at Google/Amazon/Meta?
Frequency counting and string reordering problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often test knowledge of hash tables, heaps, and bucket sort techniques for efficiently ordering elements by frequency.
What data structure is used in Sort Characters By Frequency?
The core data structure is a HashMap (or frequency array) used to count character occurrences. Depending on the solution, the ordering step uses sorting, a max heap (priority queue), or bucket sort to arrange characters by decreasing frequency.
What is the time complexity of Sort Characters By Frequency?
The HashMap plus sorting approach runs in O(n log k) time, where n is the string length and k is the number of distinct characters. Using bucket sort reduces the complexity to O(n) because characters are placed into frequency-indexed buckets instead of being comparison-sorted.

Ready to solve this problem?

Practice Sort Characters By Frequency with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Pairs Of Similar Strings

Next

First Unique Character in a String