**Explanation**

The idea to this question is to use Bucket Sort, taking advantage of the fact that the minimum and maximum frequencies a character in *s* can occur are 0 and *s.length()*, respectively.

- Construct a dictionary, that maps each distinct character to it's frequency in
*s*. - Create an array of lists,
*freqs*, with size*s.length()*+1. The index of a list in freqs is very informative. Suppose freqs[4] = { 'a', 'b', 'c' }. This means characters*a, b, c*occur 4 times each in*s*. Populate*freqs*with data from the dictionary in step 1). - Generate our solution using the
*freqs*array. This step runs in O(n), since we scan through all*s.length()+1*indices of*freqs*, and in total the number of characters to append is*s.length()*: O(n) + O(n) = O(n).

**Time Complexity**

The time complexity is O(n) where n is the number of characters in *s*, since steps 1, 2, 3 all run in O(n) time.

```
class Solution {
public String frequencySort(String s) {
// 1. Maps character to its frequency
Map<Character, Integer> charMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
Integer count = charMap.get(c);
if (count == null) {
charMap.put(c, 1);
} else {
charMap.put(c, count + 1);
}
}
// 2. Use Bucket Sort - index indicates frequency
ArrayList<Character> [] freqs =
new ArrayList[s.length() + 1];
for (char c : charMap.keySet()) {
int freq = charMap.get(c);
if (freqs[freq] == null) {
freqs[freq] = new ArrayList<>();
}
freqs[freq].add(c);
}
// 3. Build our end-result string
StringBuilder sb = new StringBuilder();
for (int i = freqs.length - 1; i >= 1; i--) {
if (freqs[i] != null) {
for (Character c : freqs[i]) {
// Append the character i amount of times
for (int j = 0; j < i; j++) {
sb.append(c);
}
}
}
}
return new String(sb);
}
}
```