# Easy to understand Java solution w/ inline comments

• 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()) {
}

// 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.

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