Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Sort Characters By Frequency

Sort Characters By Frequency

Master this topic with zero to advance depth.

Sort Characters By Frequency

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.

Visual Representation

s = "tree" Frequency Count: 'e': 2 't': 1 'r': 1 Sorted by frequency: 'e' -> 't' -> 'r' Result: "eetr" or "eert"
Medium

Examples

Input: s = "tree"
Output: "eert"
Input: s = "cccaaa"
Output: "aaaccc"
Approach 1

Level I: Max-Heap (Standard)

Intuition

Count the frequency of each character. Then, construct a Max-Heap where the key is the frequency. Repeatedly pop the character with the highest frequency and append it to our result string the required number of times.

Thought Process

  1. Use a hash map to count character frequencies.
  2. Add all (frequency, character) pairs to a Max-Heap.
  3. Poll characters from the heap and append each to a StringBuilder frequency times.
  4. Return the constructed string.
⏱ O(N log k) where k is the number of unique characters💾 O(N)

Detailed Dry Run

s = "tree"

  1. Map: {'t':1, 'r':1, 'e':2}
  2. Max-Heap: [('e',2), ('t',1), ('r',1)]
  3. Pop ('e',2). Appended 2 times -> "ee"
  4. Pop ('t',1). Appended 1 time -> "eet"
  5. Pop ('r',1). Appended 1 time -> "eetr" Result: "eetr"
java
import java.util.*;
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
        PriorityQueue<Character> pq = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        pq.addAll(map.keySet());
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            char c = pq.poll();
            for (int i = 0; i < map.get(c); i++) sb.append(c);
        }
        return sb.toString();
    }
}
Approach 2

Level II: Sorting Map Entries

Intuition

Collect character frequencies in a map, convert the map entries to a list, and sort the list by frequency in descending order. Then build the string based on the sorted list.

⏱ O(N + K log K)💾 O(K)

Detailed Dry Run

s = "tree"

  1. Map: {'t':1, 'r':1, 'e':2}
  2. List of entries: [('t',1), ('r',1), ('e',2)]
  3. Sorted List: [('e',2), ('t',1), ('r',1)]
  4. Result: "eetr"
java
import java.util.*;
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort((a, b) -> b.getValue() - a.getValue());
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list) {
            for (int i = 0; i < entry.getValue(); i++) sb.append(entry.getKey());
        }
        return sb.toString();
    }
}
Approach 3

Level III: Bucket Sort (Optimal)

Intuition

Since the maximum frequency a character can have is the length of the string N, we can use an array of lists as buckets. bucket[i] stores characters that appear exactly i times.

⏱ O(N)💾 O(N)

Detailed Dry Run

s = "tree", N=4

  1. Map: {'t':1, 'r':1, 'e':2}
  2. Buckets array of size 5: [0:[], 1:['t','r'], 2:['e'], 3:[], 4:[]]
  3. Iterate from 4 down to 1.
  4. i=2: bucket contains 'e'. Append 'e' 2 times -> "ee"
  5. i=1: bucket contains 't','r'. Append 't' 1 time, 'r' 1 time -> "eetr"
java
import java.util.*;
public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) counts.put(c, counts.getOrDefault(c, 0) + 1);
        List<Character>[] buckets = new List[s.length() + 1];
        for (Character key : counts.keySet()) {
            int freq = counts.get(key);
            if (buckets[freq] == null) buckets[freq] = new ArrayList<>();
            buckets[freq].add(key);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = buckets.length - 1; i > 0; i--) {
            if (buckets[i] != null) {
                for (char c : buckets[i]) {
                    for (int j = 0; j < i; j++) sb.append(c);
                }
            }
        }
        return sb.toString();
    }
}
← Previous QuestionFind K Pairs with Smallest Sums
Next Question →Minimum Cost to Connect Sticks