# Java O(n) solution

• ``````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();
}
}
``````

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