prehuffman.java

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

//treertt.
// t : 3
// r : 2
// e : 2
// . : 1

// ttteerr.

// SortByFreq -> tiempo: O(N Log N) espacio O(N)
// armar las frecuencias O(N)
//      V1: todos contra todos O(N^2)
//      V2: Map O(N) -> HashMap, si utilizo un TreeMap(N Log N)
// Priorizar O(N Log N)
//      V1: PriorityQueue insertar 1 elemento O(Log N) -> insertar N elementos O(N Log N) espacio (N)
//      V2: Sort con funcion custon tiempo: O(N Log N) espacio O(N)
// Construir nuevo string O(N Log N)
//      Paso1, V1: Consumir PriorityQueue, sacar 1 elemento O(Log N) -> Sacar N elementos O(N Log N)
//      Paso1,V2: Consuir elemento por elemento del array ordenado 
//      Paso2: Construir string


// MAP -> [key] -> value
// TDA -> Tipo de dato abstracto
//    1. Hash Table O(~1) --> NO NECESITO RECORRER LAS LLAVES EN ORDEN 
//    2. Autobalanced Tree (AVL, B, B+, 2-3, etc) O(Log N) --> NECESITO RECORRER LAS LLAVES EN ORDEN 

// Map<stirng, int>  map = new HashMap<>()
// Map<string, int> map = new TreeMap<>()

class Result {

    /*
     * Complete the 'SortByFreq' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts STRING s as parameter.
     */

    public static class Pair<K, V> {
        private K first;
        private V second;;

        public Pair(K first, V second) {
            this.first = first;
            this.second = second;
        }

        public K  first() {return this.first;}
        public V second() {return this.second;}
    }
    
    public static String SortByFreq(String s) {
        // Armar las frecuencias
        Map<Character, Integer> freq = new HashMap<>();
        for(char c: s.toCharArray()) {
            if(freq.containsKey(c)) {
                freq.put(c, freq.get(c) + 1);
            } else {
                freq.put(c, 1);
            }
        } 
        
        PriorityQueue<Pair<Character, Integer>> pq = new PriorityQueue<>(freq.size() > 0 ? freq.size():1, (Pair<Character, Integer> a, Pair<Character, Integer>  b) -> {
            if(a.second() != b.second()) return b.second() - a.second();
            else return a.first() - b.first();
        });
        
        
        for(Map.Entry<Character, Integer> entry: freq.entrySet()) {
            pq.add(new Pair<Character, Integer>(entry.getKey(), entry.getValue()));
        }
        
        String out = "";
        while(pq.size() > 0) {
            Pair<Character, Integer> p = pq.poll();
            for(int i=0;i<p.second();i++) out += p.first();
        }
        
        return out;
    }
    

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String s = bufferedReader.readLine();

        String res = Result.SortByFreq(s);

        bufferedWriter.write(res);
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}