451. Sort Characters By Frequency

How to solve Sort Characters By Frequency (LeetCode 451): the approach in brief

The problem

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.

Pattern

Sort Characters By Frequency is a Heap (Priority Queue) Patterns problem, in the Top K Elements (Selection/Frequency) subpattern. The pattern covers top K elements, K-way merge, two heaps for median, and scheduling

Find top K elements using heap. Solve kth largest, top K frequent, and k closest points problems.

Approach outline

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.

Complexity

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

Asked at

Sort Characters By Frequency has been reported in interviews at Bloomberg, Amazon, Facebook.