Log inSign up
mediumLeetCodeNot Started

Frequency Sort

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

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 multiple valid answers exist, return any of them.

Example 1 · Example 1: Basic Frequency:

Input: s = 'tree'
Output: 'eert'
Explanation: e appears twice, r and t appear once each. eert or eetr are both valid answers.\n\nMax-Heap by Frequency:\n (e: 2)\n / \\n (r: 1) (t: 1)

Example 2 · Example 2: All Same Frequency:

Input: s = 'cccaaa'
Output: cccaaa
Explanation: Both c and a appear three times. aaaccc is also valid.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand when Bucket Sort beats comparison-based sorting.
  • Implement Max-Heap on custom structures across all 4 languages.
  • Master frequency-based string reconstruction.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sort elements by frequency.
  • Characters with equal frequencies can appear in any order.
  • Alphabet size is bounded (ASCII).

Algorithmic Decision Tree:

  • Heap-based sorting is great when finding Top K.
  • Bucket sort is optimal when sorting the entire collection by frequency in O(N).

Connected Patterns:

Top K Frequent ElementsTop K Frequent Words

1. Brute Force — Sort Characters Directly with Frequency Comparator

Intuition

Build a frequency table. Sort the array of characters where a comes before b if freq[a] > freq[b], breaking ties with character order.

When to apply: When simplicity is preferred for short strings.

Algorithm

  1. Step 1: Count frequency of each character in s using a hash map.
  2. Step 2: Convert s to a list of characters.
  3. Step 3: Sort list using custom comparator: freq[b] - freq[a].
  4. Step 4: Join characters and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5#include <algorithm>
6using namespace std;
7
8class Solution {
9public:
10 string frequencySort(string s) {
11 unordered_map<char, int> freq;
12 for (char c : s) freq[c]++;
13
14 sort(s.begin(), s.end(), [&](char a, char b) {
15 if (freq[a] != freq[b]) return freq[a] > freq[b];
16 return a < b;
17 });
18 return s;
19 }
20};
21
22int main() {
23 Solution sol;
24 cout << "Frequency Sort (Brute Force): " << sol.frequencySort("tree") << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) sorting all characters.
  • Space complexity: O(N) — O(N) for character array and frequency map.

Why Brute Force Doesn't Scale:

For N = 5 * 105, O(N log N) requires ~9.5 * 106 operations, whereas Bucket Sort takes ~5 * 105 operations.

Bucket sort runs in ~25ms on 500,000 characters.

2. Better — Max-Heap of (Frequency, Character)

Intuition

Count frequencies in hash map. Push pairs of (freq, char) into a Max-Heap. Pop each pair and append char repeated freq times.

When to apply: When using standard heap primitives and K (unique chars) is small.

Algorithm

  1. Step 1: Compute frequencies using hash map.
  2. Step 2: Push (freq, char) pairs into a Max-Heap.
  3. Step 3: Pop each pair and append char multiplied by frequency to result.
  4. Step 4: Return result string.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5#include <queue>
6using namespace std;
7
8class Solution {
9public:
10 string frequencySort(string s) {
11 unordered_map<char, int> freq;
12 for (char c : s) freq[c]++;
13
14 priority_queue<pair<int, char>> maxHeap;
15 for (auto& [c, count] : freq) {
16 maxHeap.push({count, c});
17 }
18
19 string result = "";
20 while (!maxHeap.empty()) {
21 auto [count, c] = maxHeap.top();
22 maxHeap.pop();
23 result.append(count, c);
24 }
25 return result;
26 }
27};
28
29int main() {
30 Solution sol;
31 cout << "Frequency Sort (Max-Heap): " << sol.frequencySort("tree") << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N + K log K) — O(N + K log K) which is practically O(N) when K is constant.
  • Space complexity: O(N) — O(N) for result string.

3. Optimal — Bucket Sort (Linear Time)

Intuition

Because frequency cannot exceed string length N, allocate an array of buckets from index 0 to N. Insert each character into buckets[freq[c]]. Then iterate from N down to 1 and append characters.

When to apply: Optimal standard for linear time frequency sorting.

Algorithm

  1. Step 1: Count frequency of each character in hash map.
  2. Step 2: Create bucket array of size s.length + 1.
  3. Step 3: For each (char, count): add char to bucket[count].
  4. Step 4: Loop i from s.length down to 1. For each char in bucket[i], append char i times.
  5. Step 5: Return result string.

Interactive Trace for Frequency Sort

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Frequency map built: 'e': 2, 'r': 1, 't': 1
Visual state
Values and pointers at this exact step
tree
Root: ('e', 2)
2
Child: ('r', 1)
1
Child: ('t', 1)
1

Node order shown; add connections to display explicit tree edges.

pop: h1
Check / comparison
Max frequency is 2 (char 'e').
Decision / next transition
Pop ('e', 2) and append 'e' twice.
Why this step matters

Step 1: Frequency map built: e: 2, r: 1, t: 1. Heap initialized with (e, 2) at root.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5using namespace std;
6
7class Solution {
8public:
9 string frequencySort(string s) {
10 unordered_map<char, int> freq;
11 for (char c : s) freq[c]++;
12
13 int n = s.size();
14 vector<vector<char>> buckets(n + 1);
15 for (auto& [c, count] : freq) {
16 buckets[count].push_back(c);
17 }
18
19 string result = "";
20 for (int count = n; count >= 1; count--) {
21 for (char c : buckets[count]) {
22 result.append(count, c);
23 }
24 }
25 return result;
26 }
27};
28
29int main() {
30 Solution sol;
31 cout << "Frequency Sort (Bucket Sort): " << sol.frequencySort("tree") << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N) — O(N) linear time without any comparison sorting.
  • Space complexity: O(N) — O(N) to store frequency buckets.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Sort Characters via Frequency MapO(N log N)O(N)Count frequencies in a map. Sort the string directly using a custom comparator comparing frequencies.Sorting N characters.
2.Better — Max-Heap of Pairs (Frequency, Char)O(N + K log K)O(N)Count frequencies. Push (freq, char) for each unique character into a Max-Heap. Pop all and rebuild string.Heap operations for K characters.
3.Optimal — Bucket Sort (Frequency Indexing)OptimalO(N)O(N)Count frequencies. Create bucket array of size N + 1 where bucket[f] contains chars with frequency f. Traverse from N down to 1.None. Perfectly optimal.

Common Pitfalls & Crucial Edge Cases

Overwriting buckets

Multiple characters can share the exact same frequency, so each bucket must be a list/vector.

Treating upper/lower case as identical

A != a.

Inefficient string concatenation

In Java/Python/JS, avoid repetitive string concatenation in loops; use StringBuilder / join.

Crucial Edge Cases to Validate:

  • Single character string — Returns unchanged.
  • All characters unique — Returns any permutation.
  • All identical characters — Returns original string directly.
  • Case sensitivity — A and a are treated as distinct characters.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention Max-Heap first, then present Bucket Sort as the optimal linear O(N) upgrade.
  2. Emphasize using StringBuilder / array joins to prevent quadratic string concatenation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is Bucket Sort able to sort characters by frequency in linear O(N) time?

Back to DSA Sheet