Simple Java solution O(nlogn) beats 78%


  • 0
    S
        public String frequencySort(String s) {
            int []frequency = new int[256];
    
            for(char c: s.toCharArray())
                frequency[c]++;
    
            //1. Construct frequency map
            HashMap<Integer, StringBuilder> map = new HashMap<>();
            char c = 0; c--;
            for(int freq: frequency){
                c++; // we always want to start at 0
                if(freq == 0 ) continue;
                StringBuilder value = map.get(freq);
                if(value == null) { // key doesnt exist
                    value = new StringBuilder();
                }
                for(int count = 0; count < freq; count++) value.append(c);
    
                map.put(freq,value);
            }
    
            //2. Sort frequency and print characters in Desc order
            StringBuilder sb = new StringBuilder();
            Arrays.sort(frequency);
            int prev = 0;
            for(int freq: frequency) { // take only unique frequency as we have already repeated chars based on frequency
                if(freq > 0 && freq != prev) sb.append(map.get(freq));
                prev = freq;
            }
            return sb.reverse().toString();
        }
    

Log in to reply
 

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