451. Sort Characters By Frequency

Sort Characters By Frequency (LeetCode 451) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Top K Elements (Selection/Frequency) subpattern.

How to solve Sort Characters By Frequency

Sort Characters By Frequency is a Top K Elements problem, part of Heap (Priority Queue) Patterns. Find top K elements using heap. Solve kth largest, top K frequent, and k closest points problems.

Work towards the solution in these steps:

1. Start by counting the frequency of each character in the string to understand how often each appears.
2. Consider using a data structure that can efficiently keep track of characters sorted by their frequency counts.
3. A max heap (priority queue) can help you extract characters starting from the highest frequency to the lowest.

The reference solution runs in O(N) time and O(N) space.

The Sort Characters By Frequency solution and editorial walks through the full approach with reference code.

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.

Topics and companies

Topics: Hash Table, String, Sorting, Heap (Priority Queue), Bucket Sort, Counting.

Reported in interviews at Bloomberg, Amazon, Facebook.

How to practise Sort Characters By Frequency on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N) time and O(N) space.

Open Sort Characters By Frequency in the code editor, or read the Sort Characters By Frequency editorial for a worked solution with its approach and complexity analysis.

Where Sort Characters By Frequency sits in the DSA pattern sheet

• Heap (Priority Queue) Patterns pattern guide
• Top K Elements (Selection/Frequency) subpattern
• The full DSA patterns sheet

Problems related to Sort Characters By Frequency

Other problems that use the same Top K Elements (Selection/Frequency) and Heap (Priority Queue) Patterns techniques:

• K Closest Points to Origin — Medium, same subpattern
• Kth Largest Element in an Array — Medium, same subpattern
• Kth Largest Element in a Stream — Easy, same subpattern
• Last Stone Weight — Easy, same subpattern
• Relative Ranks — Easy, same subpattern
• Take Gifts From the Richest Pile — Easy, same subpattern

Sort Characters By Frequency FAQ