Problem Statement

Given a string s, sort it in decreasing order based on the frequency of characters and return the resulting string.

Example 1:
Input: "tree"
Output: "eert" or "eetr"
Explanation: 'e' appears twice, 'r' and 't' appear once each.

Example 2:
Input: "cccaaa"
Output: "cccaaa" or "aaaccc"
Explanation: 'c' and 'a' both appear three times. Order among same frequency characters can vary.

Constraints:

• 1 <= s.length <= 5 * 10^5
• s consists of English letters, digits, and symbols.

---

Approach in Plain English

1. Count the frequency of each character using a HashMap.
2. Use a priority queue (max-heap) to sort characters by frequency:
   • Higher frequency → higher priority.
3. Pop characters from the heap and append them to a StringBuilder multiple times equal to their frequency.
4. Convert StringBuilder to string and return.

Key idea: A max-heap ensures we always process the most frequent characters first.

Alternative approach:

• Use bucket sort if the string is large and frequency is small.
• Each bucket stores characters with same frequency → build string from highest to lowest frequency.

---

Beginner-Friendly Dry Run

Take input: "tree"

1. Count frequency:

't' → 1
'r' → 1
'e' → 2

2. Max-heap based on frequency:

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

3. Build string:

• Pop (e,2) → append "ee" → result = "ee"
• Pop (t,1) → append "t" → result = "eet"
• Pop (r,1) → append "r" → result = "eetr"

Output: "eert" or "eetr"

---

Textual Approach

• Use HashMap<Character, Integer> to count characters.
• Use PriorityQueue<Map.Entry<Character,Integer>> sorted by frequency.
• While queue not empty:
  • Poll entry (char, freq).
  • Append character freq times to StringBuilder.
• Return StringBuilder as string.

---

Java Code (Using PriorityQueue)

import java.util.*;

public class FrequencySort {

    public static String frequencySort(String s) {
        // Step 1: Count frequency
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        // Step 2: Max-heap based on frequency
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue()
        );
        maxHeap.addAll(freqMap.entrySet());

        // Step 3: Build result string
        StringBuilder sb = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> entry = maxHeap.poll();
            for (int i = 0; i < entry.getValue(); i++) {
                sb.append(entry.getKey());
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        String s1 = "tree";
        System.out.println(frequencySort(s1)); // Output: "eert" or "eetr"

        String s2 = "cccaaa";
        System.out.println(frequencySort(s2)); // Output: "cccaaa" or "aaaccc"
    }
}

---

Key Points

• HashMap counts characters efficiently.
• PriorityQueue (max-heap) ensures characters with higher frequency are processed first.
• Time Complexity: O(n log k) → n = length of string, k = number of unique characters.
• Space Complexity: O(k) → for map and heap.
• Alternative: Bucket sort → O(n) if frequency range is small.