Sort characters by frequency

Problem Link

Sort Characters By Frequency – LeetCode

Problem: Sort Characters By Frequency

Problem Statement

Given a string s, sort it in decreasing order based on the frequency of characters. Return the sorted string.

If multiple characters have the same frequency, you can return them in any order.

Examples

Example 1
Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice, 'r' and 't' once each. "eetr" is also valid.

Example 2
Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times. Either can come first.

Example 3
Input: s = "Aabb"
Output: "bbAa"
Explanation: 'b' appears twice, 'A' and 'a' once each. "bbaA" is also valid. Case is significant.

Constraints

• 1 <= s.length <= 5 * 10⁵

• s consists of uppercase and lowercase English letters and digits.

Intuition

We need to sort characters by their frequency of occurrence in descending order. This requires counting each character's frequency and then retrieving them in order from highest to lowest frequency, which can be efficiently done using a max-heap.

Approach

1. Count Frequencies: Use a HashMap<Character, Integer> to store frequencies of each character in the string.

2. Build Max-Heap: Create a PriorityQueue<Pair> where Pair stores a character and its frequency, and the heap is sorted by frequency in descending order.

3. Build Result: Poll characters from the heap and append them to a StringBuilder freq times.

4. Return the final string.

Code (Java)

import java.util.*;

class Pair {
    char ch;
    int freq;

    public Pair(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }
}

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> b.freq - a.freq);
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            pq.add(new Pair(entry.getKey(), entry.getValue()));
        }

        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Pair top = pq.poll();
            for (int i = 0; i < top.freq; i++) {
                sb.append(top.ch);
            }
        }

        return sb.toString();
    }
}

Time and Space Complexity

• Time Complexity: O(n log k)

  • O(n) for counting character frequencies

  • O(k log k) for heap operations (k = number of unique characters)

  • O(n) for building the result string

  • Overall O(n log k), but since k ≤ 62 (26 lowercase + 26 uppercase + 10 digits), it behaves like O(n)

• Space Complexity: O(n)

  • HashMap stores up to O(k) entries

  • Heap stores O(k) entries

  • Output string is of length n

Dry Run

Input: s = "tree"

• Frequency map: {t:1, r:1, e:2}

• Heap after insertion: [(e,2), (t,1), (r,1)]

• Poll e → append 'ee'

• Poll t → append 't'

• Poll r → append 'r'

• Final string: "eetr" (or "eert")

Conclusion

This problem is a classic application of frequency counting and a max-heap to order characters efficiently. It demonstrates how to use custom objects (Pair) with a priority queue and is frequently asked in interviews to test understanding of heap-based sorting strategies.