# Java O(n) Bucket Sort Solution / O(nlogn) PriorityQueue Solution, easy to understand

• The logic is very similar to NO.347 and here we just use a map a count and according to the frequency to put it into the right bucket. Then we go through the bucket to get the most frequently character and append that to the final stringbuilder.

``````public class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
List<Character> [] bucket = new List[s.length() + 1];
for (char key : map.keySet()) {
int frequency = map.get(key);
if (bucket[frequency] == null) {
bucket[frequency] = new ArrayList<>();
}
}
StringBuilder sb = new StringBuilder();
for (int pos = bucket.length - 1; pos >=0; pos--) {
if (bucket[pos] != null) {
for (char num : bucket[pos]) {
for (int i = 0; i < map.get(num); i++) {
sb.append(num);
}
}
}
}
return sb.toString();
}
}

``````

And we have normal way using PriorityQueue as follows:

``````public class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
new Comparator<Map.Entry<Character, Integer>>() {
@Override
public int compare(Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) {
return b.getValue() - a.getValue();
}
}
);
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) {
Map.Entry e = pq.poll();
for (int i = 0; i < (int)e.getValue(); i++) {
sb.append(e.getKey());
}
}
return sb.toString();
}
}
``````

• This post is deleted!

• Nice bucket sort solution!

• Why is the PQ solution's run time if O(nlogn) but not O(n)? After all you can only can constant number of chars.

• Actually, the last loop

`````` for (int i = 0; i < map.get(num); i++) {
sb.append(num);
}
``````

can be changed with

`````` for (int i = 0; i < pos; i++) {
sb.append(num);
}
``````

Since each char's frequency are the position in the bucket[];

• Hi,

I have a question related to the complexity. That is since the set of character must be in a constant space whose size is either 128 or 256 or... Will we still treat the complexity of insertion into the heap as O(logn)? Or should we treat it as constant?

• @DonaldTrump IMHO it's because poll() itself is O(nlogn) and even tho we only have a limited number of entries in the PriorityQueue, the number isn't input independent

• You can add a max to save the space.

``````public class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
int max = 0;
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
max = Math.max(max, map.get(c));
}
List<Character> [] bucket = new List[max + 1];
for (char key : map.keySet()) {
int frequency = map.get(key);
if (bucket[frequency] == null) {
bucket[frequency] = new ArrayList<>();
}
}
StringBuilder sb = new StringBuilder();
for (int pos = bucket.length - 1; pos >=0; pos--) {
if (bucket[pos] != null) {
for (char num : bucket[pos]) {
for (int i = 0; i < map.get(num); i++) {
sb.append(num);
}
}
}
}
return sb.toString();
}
}``````

• The PriorityQueue Method is O(n) as well because you have only constant number (at most 52) of Map.Entry to maintain. The bottleneck is the first for loop which is O(n).

• Useful solution. Thank you.
Maybe we can save a little bit of memory by using a freq array of size 128 instead of a map and pairing it up with a bitset to account for duplicate characters.

``````public String frequencySort(String s) {
if(s==null || s.length()<3) return s;
int[] arr1 = new int[128];
for(int i=0; i<s.length(); i++) {
char c = s.charAt(i);
arr1[c]++;
}
List<Character>[] arr2 = new List[s.length()+1];
BitSet b = new BitSet(128);
for(int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if(b.get(c)) continue;
b.set(c);
int idx = arr1[c];
if(arr2[idx]==null) {
arr2[idx] = new ArrayList<> ();
}
}
StringBuilder sb = new StringBuilder();
for(int i=arr2.length-1; i>=0; i--) {
if(arr2[i]!=null) {
for(char c : arr2[i])
for(int j=0; j<i; j++)
sb.append(c);
}
}
return sb.toString();
}
``````

• what if when the frequency is the same, then order by the alphabetic order.

for example input: acaacbb output: aaabbcc

How to achieve that?

• Anyone can tell me why I got the LTE? Thx

``````public String frequencySort(String s) {
if(s == null || s.length() <= 1)
return s;

Map<Character, String> map = new HashMap<>();
for(char c: s.toCharArray()){
map.put(c, map.getOrDefault(c, "") + c);
}

PriorityQueue<Map.Entry<Character, String>> pq = new PriorityQueue<>(
new Comparator<Map.Entry<Character, String>>() {
@Override
public int compare(Map.Entry<Character, String> a, Map.Entry<Character, String> b) {
return b.getValue().length() - a.getValue().length();
}
}
);

StringBuilder sb = new StringBuilder();
while(!pq.isEmpty()){
sb.append(pq.poll().getValue());
}

return sb.toString();
}``````

• @WhyTalent
FYI

I also use HashMap + PriorityQueue but with a more concise data structure like you.

However, my solution got TLE first. After changing all the String to StringBuilder, I got accepted! It's quite interesting in the performance gap between `+=` in String and `append()` in StringBuilder.

``````public class Solution {
public String frequencySort(String s) {
Map<Character, StringBuilder> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
map.put(c, map.getOrDefault(c, new StringBuilder()).append(c));
}

PriorityQueue<StringBuilder> queue = new PriorityQueue<>((a, b) -> (b.length() - a.length()));

StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
sb.append(queue.poll());
}
return sb.toString();
}
}
``````

• @bun919tw Yeah, you're right. thx

• A bit of Java 8.

``````public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();

IntStream.range(0, s.length()).forEach(i -> map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1));

PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());