Java O(n) solution


  • 1
    M
    public class Solution {
        public String frequencySort(String s) {
            int[] charMap = new int[256];
            for(int i=0; i<s.length(); i++){
                charMap[s.charAt(i)]++;
            }
            List<Character>[] freqMap = new ArrayList[s.length()+1];
            for(int i=0; i<charMap.length; i++){
                if(charMap[i]>0){
                    if(freqMap[charMap[i]]==null){
                        freqMap[charMap[i]] = new ArrayList<Character>();
                    }
                    freqMap[charMap[i]].add((char)i);
                }
            }
            StringBuilder res = new StringBuilder(s.length());
            for(int i=freqMap.length-1; i>=0; i--){
                if(freqMap[i]!=null){
                    for(char ch : freqMap[i]){
                        for(int j=0; j<i; j++){
                            res.append(ch);
                        }
                    }
                }
            }
            return res.toString();
        }
    }
    

Log in to reply
 

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