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)