# Java 2 solutions, using map

• Time: O(nlgn), Space: O(n)

``````public class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
Integer freq = map.getOrDefault(c, 0);
map.put(c, freq+1);
}
Tuple[] tuples = new Tuple[map.size()];
int i=0;
for(Map.Entry<Character, Integer> entry : map.entrySet()){
tuples[i] = new Tuple(entry.getKey(), entry.getValue());
i++;
}
Arrays.sort(tuples);
StringBuilder sb = new StringBuilder();
for(Tuple tup : tuples){
for(int t=0; t<tup.freq; t++){
sb.append(tup.c);
}
}
return sb.toString();
}

class Tuple implements Comparable<Tuple>{
char c;
int freq;
Tuple(char c, int freq){
this.c = c;
this.freq = freq;
}
@Override
public int compareTo(Tuple tup){
return tup.freq-freq;
}
}

}
``````

Time: O(n), Space: O(n + maxFreq)

``````public class Solution {
public String frequencySort(String s) {
if(s==null || s.length()<=1) return s;
Map<Character, Integer> map = new HashMap<>();
int maxFreq = 0;
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
Integer freq = map.getOrDefault(c, 0) + 1;
map.put(c, freq);
maxFreq = Math.max(maxFreq, freq);
}
StringBuilder[] arr = new StringBuilder[maxFreq+1];
for(Map.Entry<Character, Integer> entry : map.entrySet()){
int freq = entry.getValue();
char c = entry.getKey();
if(arr[freq] == null)
arr[freq] = new StringBuilder();
for(int i=0; i<freq; i++)
arr[freq].append(c);
}
StringBuilder sb = new StringBuilder();
for(int i=maxFreq; i>0; i--){
if(arr[i] != null)
sb.append(arr[i].toString());
}
return sb.toString();
}
}
``````

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