5
\$\begingroup\$

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();
    }
\$\endgroup\$
5
\$\begingroup\$

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()) {
            charsByFrequency.add(new TreeSet());
        }
        charsByFrequency.get(freq).add(ch);
        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();
}
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ – Charles Yang May 24 '20 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.