-
Notifications
You must be signed in to change notification settings - Fork 56
/
Solution.java
37 lines (34 loc) · 1.34 KB
/
Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package g0401_0500.s0451_sort_characters_by_frequency;
// #Medium #String #Hash_Table #Sorting #Heap_Priority_Queue #Counting #Bucket_Sort
// #Data_Structure_II_Day_21_Heap_Priority_Queue
// #2022_07_18_Time_13_ms_(89.63%)_Space_43.3_MB_(87.60%)
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
TreeMap<Integer, List<Character>> reverseMap = new TreeMap<>(Collections.reverseOrder());
for (Map.Entry<Character, Integer> c : map.entrySet()) {
int freq = map.get(c.getKey());
reverseMap.computeIfAbsent(freq, k -> new ArrayList<>());
reverseMap.get(freq).add(c.getKey());
}
StringBuilder sb = new StringBuilder();
for (Map.Entry<Integer, List<Character>> freq : reverseMap.entrySet()) {
List<Character> list = reverseMap.get(freq.getKey());
for (char c : list) {
for (int i = 0; i < freq.getKey(); i++) {
sb.append(c);
}
}
}
return sb.toString();
}
}