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.

Analysis:

Create new class charWithCount, stores char, and its count.

Scan string, use a map to store char - charWithCount objects.

Scan through values() of the map and offer all objects to MaxHeap. Comparator is comparing the count field of the object.

Another loop to scan poll() objects from maxheap and use StringBuilder to build the output.

Code:

public class Solution {
    public String frequencySort(String s) {
        if(s == null || s.length() == 0)
        {
            return "";
        }
        Queue<charWithCount> maxHeap = new PriorityQueue<charWithCount>(52, new Comparator<charWithCount>(){
            @Override
            public int compare(charWithCount a, charWithCount b)
            {
                if(a.count == b.count)
                {
                    return 0;
                }
                return a.count<b.count ? 1 : -1;
            }
        });

        Map<Character, charWithCount> map = new HashMap<Character, charWithCount>();

        for(int i=0; i< s.length(); i++)
        {
            char cur = s.charAt(i);
            if(!map.keySet().contains(cur))
            {
                map.put(cur, new charWithCount(cur));
            }
            map.get(cur).count++;
        }

        for(charWithCount itr : map.values())
        {
            maxHeap.offer(itr);
        }

        StringBuilder sb = new StringBuilder();
        while(!maxHeap.isEmpty())
        {
            charWithCount temp = maxHeap.poll();
            for(int i=0; i<temp.count;i++)
            {
                sb.append(temp.ch);
            }
        }
        return sb.toString();
    }
}

class charWithCount{
    public char ch;
    public int count = 0;
    public charWithCount(char c)
    {
        ch = c;
    }
}