public class Solution {
public String frequencySort(String s) {
//counting sort
int n = s.length();
int[] charCount = new int[256];
char[] cs = s.toCharArray();
char[] ans = new char[n];
//Count the char
for(char c: cs){
charCount[c]++;
}
//counting sort the frequency since it has range from 1 to n.
int[] count = new int[n+1];
for(int i:charCount){
if(i>0){
count[i]+=i;
}
}
for(int i=1; i<count.length; i++){
count[i] += count[i1];
}
for(int i=0; i<256; i++){
if(charCount[i] > 0){
int c = charCount[i];
// small different from normal counting sort, in case the same char has to be together
while(c>0){
ans[ncount[charCount[i]]] = (char)i;
count[charCount[i]];
c;
}
}
}
return new String(ans);
}
}
Java easy understand solution, O(n) using counting sort, beat 99%.


@nightswatch Thanks for the share. Can you explain the step 
for(int i=1; i<count.length; i++){
count[i] += count[i1];
}
Thanks.

@pantherNation
Basically, it sums up the counts for each value, so you can get a sense of how many values less than a certain value.You can also check and learn counting sort from the following links:
code: http://www.geeksforgeeks.org/countingsort/
video: https://www.youtube.com/watch?v=7zuGmKfUt7s