simple, short java bucket sort solution. O(n) time and O(1) space


  • 0
    C
    public String frequencySort(String s) {
            if(s.length()==0) return "";
            int[] bucket = new int[256];
            List<int[]> list = new ArrayList<>();
            for(int i=0;i<s.length();i++) bucket[s.charAt(i)]++;
            for(int i=0;i<256;i++){
                if(bucket[i] > 0) list.add(new int[]{i, bucket[i]});
            }
            Collections.sort(list, new Comparator<int[]>(){
                public int compare(int[] a1, int[] a2){
                    return a2[1] - a1[1];
                }
            });
            StringBuilder sb = new StringBuilder();
            for(int[] c: list){
                while(c[1]-- > 0) sb.append((char)c[0]);
            }
            return sb.toString();
        }
    

Log in to reply
 

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