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 valid answer.

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();
}


You have conceived a theoretical model that works. And avoids sorting.

• Tiers by frequency
• Every tier contains letters of that frequency

It will come at no surprise, that moving a char from on frequency's bin to the next frequency's bin will cost at least as much as sorting. But it is a nice mechanism one sees too rare, and might have its application in vector operations, GPUs or whatever.

1. Improved could be the names. "Tier" one inclines to love, and might be apt, but does the term help in understanding the code?

2. Use if possible more general interfaces implemented by specific classes, like List<T> list = new ArrayList<>();. This is more flexible, when passing to methods, reimplementing with another class.

3. The comment to remain is for adding null for the frequency 0.

4. For characters in a tier use a Set. As implementation I used a TreeSet which is sorted to give nicer output.

5. Use as index not i but rather freq.

6. Moving from one frequency to the next higher can be done in two separate steps old+new. That makes the code more readable.

so:

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

List<Set<Character>> charsByFrequency = new ArrayList<>(); // stores characters at their proper frequency "tier"
Map<Character, Integer> frequencyMap = new HashMap<>(); // maps the characters to their current frequency tier
charsByFrequency.add(null); // entry for frequency 0 is not used

for (char c : s.toCharArray()) {
Character ch = c; // Does ch = Character.valueOf(c);
int oldFreq = frequencyMap.getOrDefault(c, 0);
if (oldFreq != 0) {
charsByFrequency.get(oldFreq).remove(ch);
}
int freq = oldFreq + 1;
if (freq >= charsByFrequency.size()) {
}
frequencyMap.put(ch, freq);
}

StringBuilder result = new StringBuilder();
for (int i = 1; i < charsByFrequency.size(); i++) { // iterate through tiers
Set<Character> tier = charsByFrequency.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();
}

• Thank you so much! This is a much more elaborate and thorough response than expected. I'm a first year college programming student, so all insight will probably be helpful. May 24, 2020 at 20:34