Easy to understand Java solution w/ inline comments


  • 0
    C

    The process used has 3 steps.

    1. scan over the string once, storing the count of each character seen into a map.
    2. pair characters up with their frequency count and throw them into a priority queue to sort.
    3. empty contents of queue to build solution string and return.
    public class Solution {
        public String frequencySort(String s) {
            if(s == null) return null;
            // create a map which stores all characters of the string and their number of occurances
            Map<Character, Integer> characterFrequency= new HashMap<>();
            for (char c : s.toCharArray()) {
                if (!characterFrequency.containsKey(c)) {
                    characterFrequency.put(c, 0);
                }
                characterFrequency.put(c, characterFrequency.get(c) + 1);
            }
            
            // throw all characters seen from s into a priority queue to sort by their frequency count.
            PriorityQueue<QueueNode> pq = new PriorityQueue<QueueNode>();
            for (Character c : characterFrequency.keySet()) {
                pq.add(new QueueNode(c, characterFrequency.get(c)));
            }
            
            // our queue now stores the characters sorted by frequency.
            // build string from elements of the queue until queue is empty and return.
            StringBuilder output = new StringBuilder();
            while (!pq.isEmpty()) {
                QueueNode charInstance = pq.remove();
                for (int i = 0; i < charInstance.freq; i++) {
                    output.append(charInstance.c);
                }
            }
            return output.reverse().toString();
        }
        
        // class used to reperesent a pairing of character and it's frequency count.
        // implements comparable so elements can be sorted.
        private class QueueNode implements Comparable<QueueNode> {
            public char c;
            public int freq;
            
            // constructor
            public QueueNode(char c, int freq) {
                this.c = c;
                this.freq = freq;
            }
            
            // compareTo
            public int compareTo(QueueNode other) {
                return this.freq - other.freq;
            }
        }
    }
    

    If there's a way to pair characters and their frequency that doesn't require making a new class it would be better!
    Sorting using a priority queue is essentially a heapsort, so overall complexity would be O(slog(s)) I believe.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.