# Java Heap Solution, 9 ms beats 99%

• The idea here is:

• Count the frequency of the characters in the string
• Add the <character, count> pairs into a heap, which is sorted by the descending order of count
• Poll out the pairs one-by-one and construct the string using the StringBuilder.

The complexity is `O(N+NlogN+N) = O(NlogN)`, N is the string length.

``````public class Solution {
//Definition of pairs
class Charcount{
int count;
char c;
public Charcount(int n,char c){
this.count = n;
this.c = c;
}
}
public String frequencySort(String s) {
//Count frequency
int[] charmap = new int[128];
for(char c:s.toCharArray()){
charmap[c]++;
}
//Construct heap
Comparator<Charcount> cmp = new Comparator<Charcount>(){
public int compare(Charcount c1,Charcount c2){
return c2.count-c1.count;
}
};
Queue<Charcount> q = new PriorityQueue<Charcount>(1,cmp);//Use a constant capacity to avoid error when s==""

for(int i = 0;i<charmap.length;i++){
if(charmap[i]>0){
q.offer(new Charcount(charmap[i],(char)(i)));
}
}
//Construct string
StringBuilder sb = new StringBuilder();
while(!q.isEmpty()){
Charcount c = q.poll();
char[] line = new char[c.count];
Arrays.fill(line,c.c);
sb.append(new String(line));
}
return sb.toString();
}
}
``````

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