public class SortCharactersByFrequency {
    public static void main(String[] args) {
        System.out.println(frequencySort("Leetcode"));
    }

    public static String frequencySort(String s) {
        HashMap<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<CharacterFrequency> priorityQueue = new PriorityQueue<>();
        for (HashMap.Entry<java.lang.Character, Integer> entry : map.entrySet()) {
            priorityQueue.offer(new CharacterFrequency(entry.getKey(), entry.getValue()));
        }
        StringBuilder stringBuilder = new StringBuilder();
        while (!priorityQueue.isEmpty()) {
            CharacterFrequency characterFrequency = priorityQueue.poll();
            for (int i = 0; i < characterFrequency.frequency; i++) {
                stringBuilder.append(characterFrequency.character);
            }
        }
        return stringBuilder.toString();
    }
    static class CharacterFrequency implements Comparable<CharacterFrequency> {

        Character character;
        int frequency;

        public CharacterFrequency(java.lang.Character character, int frequency) {
            this.character = character;
            this.frequency = frequency;
        }

        @Override
        public int compareTo(CharacterFrequency that) {
            if (this.frequency > 0 || that.frequency > 0) {
                return that.frequency - this.frequency;
            }
            return that.character.compareTo(this.character);
        }
    }
}