DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Sort character by frequency

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)O(n) , O(n) for creating the map array, + O(1) for building the heap/priorityqueue, + O(n) for creating the result string.

SC: O(n)O(n) , for the priority queue of size 256 = O(1), + and O(n)O(n) 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();
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)