Leetcode 451: Sort Characters By Frequency

Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.
Example:
Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Here is my understanding and solution to the problem

One approach is to use HashMap — sort the map by values. Time complexity of this code will be O(nlgn)

Here is another approach. This is based on counting sort or bucket sort. Time complexity of this approach would be O(n).

Algorithm is as follows:

Sample input string : cwcwcrtr

Step 1: Store freq of each character. c — 3, r — 2, w — 2, t — 1

Step 2: Prepare multi storage bucket. With each storage level — characters with same frequency.

Step 3: bucket[3] = c , bucket[2] = rw , bucket[1] = t

Step 4: Merge elements with same freq in final ans.

Step 5: Ans: cccrrwwt

public String frequencySort(String s) {


    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();
    }
    // Step 3: bucket[3] = c , bucket[2] = rw , bucket[1] = t
    for (int i = 0; i < 256; i++) {

        int elemFreq = freq[i];
        if (elemFreq > 0) {
            bucketBuilder[elemFreq].
                           append(Character.toString((char) (i)));
        }

    }

    // Step 4: Merge elements with same freq/bucket level in 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();

}