# O(n) Easy to understand Java Solution

1. Build a map of characters to the number of times it occurs in the string
2. Create an array where the index of the array represents how many times that character occurred in the String
3. Iterate from the end of the array to the beginning, and at each index, append each character to the return string that number of times.
``````public String frequencySort(String s) {
if (s == null) {
return null;
}
Map<Character, Integer> map = new HashMap();
char[] charArray = s.toCharArray();
int max = 0;
for (Character c : charArray) {
if (!map.containsKey(c)) {
map.put(c, 0);
}
map.put(c, map.get(c) + 1);
max = Math.max(max, map.get(c));
}

List<Character>[] array = buildArray(map, max);

return buildString(array);
}

private List<Character>[] buildArray(Map<Character, Integer> map, int maxCount) {
List<Character>[] array = new List[maxCount + 1];
for (Character c : map.keySet()) {
int count = map.get(c);
if (array[count] == null) {
array[count] = new ArrayList();
}
}
return array;
}

private String buildString(List<Character>[] array) {
StringBuilder sb = new StringBuilder();
for (int i = array.length - 1; i > 0; i--) {
List<Character> list = array[i];
if (list != null) {
for (Character c : list) {
for (int j = 0; j < i; j++) {
sb.append(c);
}
}
}
}
return sb.toString();
}
``````

• Nice solution. For character counting we don't need a map, we can just use an array. I did it as follows:

``````public class Solution {
public String frequencySort(String s) {
int[] freq = new int [256];
for (char ch: s.toCharArray()) freq[ch]++;
TreeMap<Integer, List<Character>> tree = new TreeMap<Integer, List<Character>>();
for (int i=0; i<freq.length; i++) {
if (freq[i] > 0) {
if (!tree.containsKey(freq[i])) {
}
}
}
StringBuilder sb = new StringBuilder();
while(tree.size() > 0) {
Map.Entry<Integer, List<Character>> entry = tree.pollLastEntry();
for (Character ch: entry.getValue()) {
sb.append(new String(new char[entry.getKey()]).replace('\0', ch));
}
}
return sb.toString();
}
}
``````

• @Hx2 Thanks! You are correct if we can assume ascii 256. Good call.

• Nice O(N) time solution (and also O(N) space). Another trade-off I can think about is to go another O(N) pass in frequency map to also get min frequency instead of max frequency so that the array length to build could be much shorten if the character frequencies are very close to each other. This will also save time when building string in the expense of an additional pass in frequency to get min frequency.

• My code runs in 11ms and i think its faster than yours . I see people are using HashMap/TreeMap which are not at all required. If you know bucket sort then following solution will be easy to understand!

``````public String frequencySort(String s) {
if(s.length() < 3)
return s;
int max = 0;
int[] map = new int[256];
for(char ch : s.toCharArray()) {
map[ch]++;
max = Math.max(max,map[ch]);
}
String[] buckets = new String[max + 1]; // create max buckets
for(int i = 0 ; i < 256; i++) { // join chars in the same bucket
String str = buckets[map[i]];
if(map[i] > 0)
buckets[map[i]] = (str == null) ? "" + (char)i : (str + (char) i);
}
StringBuilder strb = new StringBuilder();
for(int i = max; i >= 0; i--) { // create string for each bucket.
if(buckets[i] != null)
for(char ch : buckets[i].toCharArray())
for(int j = 0; j < i; j++)
strb.append(ch);
}
return strb.toString();
}
``````

• @piyush121 Please include the time taken. Nice approach, expanded my toolbox(bucket sort) because of you!

• @dev.abkulkar Done! Thanks for the vote !

• @Hx2 If you treemap every operation is not o(1), it is log(n).
So time complexity increases.

• Nice Solution! Thanks for sharing. I think some part can be simplified. Here is my Java solution:

``````public String frequencySort(String s) {
int[] count = new int[256];
StringBuilder sb = new StringBuilder();
List<List<Integer>> list = new ArrayList<>();

for (int i = 0; i < s.length(); i++) count[s.charAt(i)]++;
for (int i = 0; i < s.length()+1; i++) list.add(new ArrayList<Integer>());
for (int i = 0; i < count.length; i++) if (count[i] != 0) list.get(count[i]).add(i);

for (int i = list.size()-1; i >= 0; i--){
if (list.get(i) != null){
List<Integer> temp = list.get(i);
for(int k = 0; k < temp.size(); k++){
for (int m = 0; m < i; m++){
sb.append(Character.toChars(temp.get(k)));
}
}
}
}
return sb.toString();
}``````

• Could anyone told me why the time complexity is O(n) in this solution?
The buildString function doesn't seems like a O(n) method.

• Could anyone told me why the time complexity is O(n) in this solution?
The buildString function doesn't seems like a O(n) method.

The `buildString` function is still `O(N)` time complexity even though it has 3 nested loops. At the end of the day, the time complexity in function `buildString` depends on how many time `sb.append(c)` is executed. The final result string `sb.toString()` is simply a reordered string of the given string, so of course, `sb.append(c)` is executed exactly `N` times.

• @Hx2 Why is array preferable over map? Aren't they using the same amount of space?

• @Hx2 Why is array preferable over map? Aren't they using the same amount of space?

If both arrays and maps can achieve the same purpose, indeed arrays should be always preferable over maps. Even though the space usage are both `O(N)` in terms of asymptotic sense, arrays are simpler data structure with less space and contiguous memory allocation, which has better performance than maps. While maps/sets are node based containers which suffer memory locality. I am speaking for C++ and Java might differ at some level. Hopefully, it could help.

• In this instance, each pollToLastEntry is log(n), making your solution nlogn overall. You could walk through it backwards in O(n) via Collections.reverseOrder.

• @Hx2 Why not just use PriorityQueue instead of TreeSet?

• For the mapping part can be simplified

``````for (char c: s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
``````

• @Hx2 Nice solution. If we can assume ascii 256, using a 2D array could be more simple. It also works with O(n) time and O(1) space.

``````    public String frequencySort(String s) {
StringBuffer sb = new StringBuffer();
int[][] a = new int[256][2];//a[][0] is the character. a[][1] is the frequency
for(int i=0;i<256;++i)
a[i][0]=i;
char temp;
for(int i=0;i<s.length();++i){
temp = s.charAt(i);
a[temp][1]++;
}
Arrays.sort(a,new Comparator<int[]>(){
public int compare(int[] a,int[] b){
return b[1]-a[1];
}
});
for(int i=0;i<256;++i){
temp = (char)a[i][0];
for(int j=0;j<a[i][1];++j)
sb.append(temp);
}
return sb.toString();
}``````

• This post is deleted!

• Java solution use hashmap and heap.

``````public String frequencySort(String s) {
char[] sc = s.toCharArray();
Map<Character, Integer> map = new HashMap();
for(char c: sc){
int val = map.getOrDefault(c, 0) + 1;
map.put(c, val);
}

Comparator<Map.Entry<Character, Integer>> com = Map.Entry.comparingByValue(Comparator.reverseOrder());
PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue(com);

for(Map.Entry<Character, Integer> entry: map.entrySet()){
pq.offer(entry);
}

StringBuilder sb = new StringBuilder();
while(!pq.isEmpty()){
Map.Entry<Character, Integer> entry = pq.poll();
char k = entry.getKey();
int v = entry.getValue();
char[] rep = new char[v];
Arrays.fill(rep, k);
sb.append(rep);
}
return sb.toString();
}``````

• This post is deleted!

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