Skip to content

Instantly share code, notes, and snippets.

@so77id
Created October 26, 2021 20:20
Show Gist options
  • Save so77id/33cdfe00f507b451dac20ba6df8d04de to your computer and use it in GitHub Desktop.
Save so77id/33cdfe00f507b451dac20ba6df8d04de to your computer and use it in GitHub Desktop.
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment