# programming challenge – Sort Characters By Frequency Java For context, I worked on the LeetCode May 2020 Challenge Week 3 Day 1. The challenge was described as this:

Given a string, sort it in decreasing order based on the frequency of
characters.

Example 1:

Input: `"tree"`

Output: `"eert"`

Explanation: `'e'` appears twice while `'r'` and `'t'` both appear once. So
`'e'` must appear before both `'r'` and `'t'`. Therefore `"eetr"` is also a

Example 2:

Input: `"cccaaa"`

Output: `"cccaaa"`

Explanation: Both `'c'` and `'a'` appear three times, so `"aaaccc"` is also
a valid answer. Note that `"cacaca"` is incorrect, as the same
characters must be together.

Example 3:

Input: `"Aabb"`

Output: `"bbAa"`

Explanation: `"bbaA"` is also a valid answer, but `"Aabb"` is incorrect.
Note that `'A'` and `'a'` are treated as two different characters.

Anyways, I looked up some popular solutions. One was to get the frequency of each character and sort, and the other was the use a heap. I liked both of these solutions, but I wanted to make one where there was no sorting.

My solution involved an idea of an `ArrayList` of “tiers,” where the index of the tier represents the frequency. Each tier consists of an `ArrayList` containing the characters which the corresponding frequency. As letters increase in frequency, the higher frequency tier they move up. I also used a `HashMap` to keep track of which frequency tier each character was in. Upon finishing iterating through the whole string, I simply use a `StringBuilder` to append the letters starting at the bottom tier, reverse the `StringBuilder`, then return the String. I was hoping someone could give me pointers (ha, code pun) on optimizing/modifying this approach without including any kind of sorting. Below is the functional code:

``````public static String frequencySort(String s) {
if (s.length() <= 1) return s;

ArrayList<ArrayList<Character>> tieredFreq = new ArrayList<>(); // stores characters at their proper frequency "tier"
HashMap<Character, Integer> tierOfChars = new HashMap<>(); // maps the characters to their current frequency tier

for (char c : s.toCharArray()) {
tierOfChars.put(c, tierOfChars.getOrDefault(c, 0) + 1); // add char or increment the tier of the character
int i = tierOfChars.get(c); // i = tier of the character
if (tieredFreq.size() <= i) tieredFreq.add(new ArrayList<>()); // if not enough tiers, add a new tier
if (i > 1) tieredFreq.get(i - 1).remove(new Character(c)); // if c exists in previous tier, remove it
}

StringBuilder result = new StringBuilder();
for (int i = 1; i < tieredFreq.size(); i++) { // iterate through tiers
ArrayList<Character> tier = tieredFreq.get(i); // get tier
for (Character c : tier) { // for each char in tier, append to string a number of times equal to the tier
for (int j = 0; j < i; j++) result.append(c);
}
}

result.reverse(); // reverse, since result is currently in ascending order
return result.toString();
}
`````` Posted on Categories Articles