# O(n) Easy Java Solution!

• ``````1. Keep a count for every character to maintain its frequency.
2. Keep an array of Set<Character> of size n + 1, where every entry maintains the characters that appear the number of times which equals index in the array.
e.g sets[5] means all the characters that appeared 5 times.
3. Finally traverse the array of sets from right to left to build the resulting string.

public class Solution {
public String frequencySort(String s) {
if (s == null || s.length() == 0) {
return "";
}
int n = s.length();
Set<?>[] sets = new Set<?>[n + 1];
int[] count = new int[256];
for (char ch : s.toCharArray()) {
count[ch]++;
if (count[ch] > 1) {
sets[count[ch] - 1].remove(ch);
}
if (sets[count[ch]] == null) {
sets[count[ch]] = new HashSet<Character>();
}
}
StringBuilder sb = new StringBuilder();
for (int i = n; i > 0; i--) {
Set<Character> set = (Set<Character>)sets[i];
if (set != null) {
for (char ch : set) {
for (int j = 0; j < i; j++) {
sb.append(ch);
}
}
}
}
return sb.toString();
}
}

``````

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