Java O(n) solution


  • 0
    B
    public class Solution {
        public String frequencySort(String s) {
            
            // One approach is to use sorting by values in hashmap. This is O(nlogn). 
            // Bucket sort is the another technique.
            
            // Algo: cwcwcrtr
            // Store freq of each character. c - 3, r - 2, w - 2, t - 1
            // Prepare multi storage bucket. With each storage level - characters with same frequency. 
            // bucket[3] = c 
            // bucket[2] = rw
            // bucket[1] = t
            // Merge elements with same freq in final ans.
            // Ans: ccc-rrww-t
            
            int len = s.length();
            // Assuming Extended ASCII encoding.
            int [] freq = new int[256];
            
            // Step 1: Store freq of each character. c - 3, r - 2, w - 2, t - 1
            // And finding max vertical bucket levels.
            int bucketLevel = 0;
            for(int i=0; i<len; i++) {
                freq[s.charAt(i)]++;
                
                bucketLevel = Math.max(bucketLevel,freq[s.charAt(i)]);
            }
            
            // Step 2: Prepare multi storage bucket. With each storage level - characters with same frequency.
            StringBuilder [] bucketBuilder = new StringBuilder[bucketLevel+1];
            
            for(int i=0; i<bucketBuilder.length; i++) {
                bucketBuilder[i] = new StringBuilder();
            }
            
            for(int i=0; i<256; i++) {
            
               int elemFreq = freq[i];
               if(elemFreq > 0) {
                   bucketBuilder[elemFreq].append(Character.toString((char)(i)));   
               }
                
            }
            
            // Step 3: Merge elements with same freq/bucket level in final ans.
            StringBuilder ans = new StringBuilder();
            for(int i = bucketLevel; i>0; i--) {
               
               char[] levelChars = bucketBuilder[i].toString().toCharArray();
               
               for(int j=0; j<levelChars.length;j++) {
                   
                   for(int k=0;k<i;k++) {
                       ans.append(levelChars[j]);
                   }
                   
               }
                 
            }
            
            return ans.toString();
        }
    }
    

Log in to reply
 

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