Untitled

import java.util.*;

class Solution {
    public String frequencySort(String s) {
        // Step 1: Create a frequency map
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char ch : s.toCharArray()) {
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }

        // Step 2: Create a priority queue to sort characters by frequency
        PriorityQueue<Character> pq = new PriorityQueue<>(
            (a, b) -> freqMap.get(b) - freqMap.get(a) // Max-heap based on frequency
        );

        // Step 3: Add all characters to the priority queue
        for (char ch : freqMap.keySet()) {
            pq.add(ch);
        }

        // Step 4: Build the result string
        StringBuilder result = new StringBuilder();
        while (!pq.isEmpty()) {
            char ch = pq.poll();
            int freq = freqMap.get(ch);
            for (int i = 0; i < freq; i++) { // Use a for loop to append the character
                result.append(ch);
            }
        }

        return result.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1
        String s1 = "tree";
        System.out.println(solution.frequencySort(s1)); // Output: "eert" or "eetr"

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

        // Example 3
        String s3 = "Aabb";
        System.out.println(solution.frequencySort(s3)); // Output: "bbaA" or "bbAa"
    }
}