Java Heap Solution, 9 ms beats 99%

  • 0

    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()){
            //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++){
                    q.offer(new Charcount(charmap[i],(char)(i)));
            //Construct string
            StringBuilder sb = new StringBuilder();
                Charcount c = q.poll();
                char[] line = new char[c.count];
                sb.append(new String(line));
            return sb.toString();

Log in to reply

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