Java solution using TreeMap


  • 1
    A

    Store frequency of character in an array at index location, and then build a TreeMap with frequency of each character mapped to characters with that frequency. As TreeMap is ordered based on reverseOrder, so simply get Strings present at each frequency and build the final String.

    public String frequencySort(String s) {
            TreeMap<Integer, StringBuilder> tmap = new TreeMap<>(Collections.reverseOrder());
            //Store the frequency of characters in original String
            int[] freq = new int[128];
            for (int i=0; i<s.length(); i++){
                char ch = s.charAt(i);
                freq[ch]++;
            }
            //Build a TreeMap based on frequency and character that occur with same frequency.
            for(int i=0; i<128; i++){
                if(freq[i]!=0){
                    if(tmap.containsKey(freq[i])){
                        StringBuilder curr = tmap.get(freq[i]);
                        tmap.put(freq[i], curr.append((char)i + ""));
                    } else{
                        tmap.put(freq[i], new StringBuilder((char)i + ""));
                    }
                }
            }
            //Build the final String with frequency of TreeMap.
            StringBuilder res = new StringBuilder();
            for(int key: tmap.keySet()){
                StringBuilder curr = tmap.get(key);
                for(int i=0; i<curr.length(); i++){
                    for(int j=0; j<key; j++){
                        res = res.append(curr.charAt(i)+"");
                    }
                }
            }
            return res.toString();
        }
    

Log in to reply
 

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