# Java easy understand solution, O(n) using counting sort, beat 99%.

• ``````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[i-1];
}

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[n-count[charCount[i]]] = (char)i;
count[charCount[i]]--;
c--;
}

}
}

return new String(ans);
}
}
``````

• @nightswatch Thanks for the share. Can you explain the step -
for(int i=1; i<count.length; i++){
count[i] += count[i-1];
}
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:

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