Sort Characters By Frequency

Amazon

Bloomberg

2020-05-22

451. Sort Characters By Frequency

Question:

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Solution:

This problem can be solved by using hash table and PriorityQueue. The PriorityQueue can also be replaced by Bucket sort array.

Bucket Sort:

class Solution {
    public String frequencySort(String s) {
        if(s == null || s.length() == 0) return "";
        
        HashMap<Character, Integer> map = new HashMap<>();
        
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        // Using Bucket Sort
        List<Character>[] currList = new List[s.length() + 1];
        
        for (char c : map.keySet()) {
            int freq = map.get(c);
            if (currList[freq] == null) {
                currList[freq] = new ArrayList<Character>();
            }
            currList[freq].add(c);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = s.length(); i > 0; i--) {
            if (currList[i] != null) {
                for (char c : currList[i]) {
                    int printfreq = map.get(c);
                    while (printfreq-- > 0) {
                        sb.append(c);
                    }
                }
            } 
        } 
        
        return sb.toString();
    }
}

Priority Queue:

class Solution {
    public String frequencySort(String s) {
        if(s == null || s.length() == 0) return "";
        
        HashMap<Character, Integer> map = new HashMap<>();
        
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(s.length(), new Comparator<Map.Entry<Character, Integer>>(){
            @Override
            public int compare(Map.Entry<Character, Integer> e1, Map.Entry<Character, Integer> e2) {
                return e2.getValue() - e1.getValue();
            }
        });
        
        pq.addAll(map.entrySet());
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Map.Entry<Character, Integer> curr = pq.poll();
            for(int i = 0; i < curr.getValue(); i++) {
                sb.append(curr.getKey());
            }
        }
        return sb.toString();
    }
}