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
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
        tieredFreq.add(null); // tier 0

        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
            tieredFreq.get(i).add(c); // add to new tier
        }

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