# Java O(n) Easy To Understand, Optimal Solution

• 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.

1. Construct a dictionary, that maps each distinct character to it's frequency in s.
2. 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).
3. 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<>();
}
}

// 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);
}
}
``````

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