Understanding the Problem:

Given a string, our goal is to sort its characters based on their frequency. For example, for the input “tree,” the output should be “eert” or “eetr,” as both have the same characters but with different arrangements based on frequency.

Approach:

To tackle this problem, we’ll employ a HashMap to store each character’s frequency in the input string. We’ll create a custom object called Pair to store the character, its frequency, and a finalString attribute that accumulates the character based on its frequency. We’ll then iterate through the string, updating the frequency and finalString attributes of each character in the HashMap.

Next, we’ll transfer the Pair objects from the HashMap to an ArrayList for sorting. We’ll define a custom Comparator to sort the Pair objects based on their frequencies in descending order.

Finally, we’ll construct the sorted string by concatenating the finalString attribute of each Pair object in the sorted ArrayList.

Implementation:

Let’s dive into the Java implementation of the frequencySort method:

Read Also: 1695. Maximum Erasure Value

class Pair {
    int frequency;
    char character;
    String finalString;
    Pair(char c, int f) {
        character = c;
        frequency = f;
        finalString = "" + c;
    }
    public void increment() {
        frequency++;
        finalString = finalString + character;
    }
}

class Solution {
    public String frequencySort(String s) {
        char c[] = s.toCharArray();
        HashMap<Character,Pair> map = new HashMap<Character,Pair>();
        ArrayList<Pair> list = new ArrayList<Pair>();
        for(int i=0; i<c.length; i++) {
            if(map.containsKey(c[i])) {
                map.get(c[i]).increment();
            } else {
                Pair temp = new Pair(c[i], 1);
                map.put(c[i], temp);
                list.add(temp);
            }
        }
        Collections.sort(list, new SortbyFreq());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<list.size(); i++) {
            sb.append(list.get(i).finalString);
        }
        return sb.toString();
    }
    class SortbyFreq implements Comparator<Pair> { 
        public int compare(Pair a, Pair b) { 
            return b.frequency - a.frequency; 
        } 
    }
}

https://leetcode.com/problems/sort-characters-by-frequency/description/