Problem
Time Complexity: The number of distinct characters (k) can be at most 256, so inserting k elements into the priority queue will take O(k log k) time, where k ≤ 256. Therefore, this is bounded by O(256 log 256) = O(1) because it is a constant value.
TC: , O(n) for creating the map array, + O(1) for building the heap/priorityqueue, + O(n) for creating the result string.
SC:
, for the priority queue of size 256 = O(1), + and
for StringBuilder str
class Solution {
public String frequencySort(String s) {
PriorityQueue<Pair<Character, Integer>> q = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
int map[] = new int[256];//count of all the ascii characters
for (int i = 0; i < s.length(); i++) {
map[s.charAt(i)]++;
}
for (int i = 0; i < map.length; i++) {
if (map[i] >=1)
q.add(new Pair((char) i, map[i]));
}
StringBuilder str = new StringBuilder();
while (!q.isEmpty()) {
Pair<Character, Integer> p = q.remove();
int count = p.getValue();
while (count-- > 0) {
str.append(p.getKey());
}
}
return str.toString();
}
}
Top comments (0)