MockInterview:451. Sort Characters By Frequency

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.

class Solution {
    public class CharFre{
        public char c;
        public int fre;
        public CharFre(char c, int fre){
            this.c = c;
            this.fre = fre;
        }
    }
    public String frequencySort(String s) {
        Map<Character,CharFre> map = new HashMap<Character,CharFre>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            CharFre current = map.get(c);
            if(current == null){
                current = new CharFre(c,1);
                map.put(c,current);
            }else{
                current.fre++;
            }
        }
        Set<Map.Entry<Character,CharFre>> set = map.entrySet();
        int size = set.size();
        CharFre[] fre = new CharFre[size];
        int index = 0;
        for(Map.Entry<Character,CharFre> entry : set){
            fre[index] = entry.getValue();
            index++;
        }
        Arrays.sort(fre,new MyComparator());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < fre.length; i++){
            CharFre current = fre[i];
            if(current != null){
                for(int j = 0; j < current.fre; j++){
                    sb.append(current.c);
                }
            }
        }
        return sb.toString();
    }
    
    public class MyComparator implements Comparator<CharFre>{
        public int compare(CharFre f1, CharFre f2){
                if(f1.fre < f2.fre){
                    return 1;
                }else if(f1.fre > f2.fre){
                    return -1;
                }
                return 0;
        }
    }
}