bucket sort
For this problem, each frequency should be bounded in 0-len. (len is the length of the string).
To achieve the O(n), use bucket sort.
To put the same character together, use a arraylist for each bucket unit.
import java.util.ArrayList;
public class Solution {
public String frequencySort(String s) {
ArrayList[] bucket = new ArrayList[s.length() + 1];
int[] mp = new int[128];
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
mp[c]++;
}
for(int i = 0; i < mp.length; i++){
int f = mp[i];
if(f != 0){
if(bucket[f] == null){
bucket[f] = new ArrayList<Integer>();
}
bucket[f].add(i);
}
}
StringBuilder sb = new StringBuilder();
for(int i = bucket.length - 1; i > 0; i--){
if(bucket[i] == null) continue;
for(Object o : bucket[i]){
int k = (Integer)o;
for(int j = 0; j < i; j++){
sb.append((char)k);
}
}
}
return sb.toString();
}
}
notes about generics
For this bubble sort, it use some generics array. see the reference.
generics gotcha