Sort Characters By Frequency - Leetcode Solution

The problem Sort Characters By Frequency on LeetCode requires us to sort a given string in decreasing order of frequency of character occurrence. For example, for the input "tree", we need to output "eert" (since 'e' appears twice, and 't' and 'r' appear once each).

The most efficient way to solve this problem is to use a hash map to count the frequency of each character in the string. We can then sort the hash map by frequency and output the characters in the order of decreasing frequency.

Here is the step-by-step solution for the Sort Characters By Frequency problem on LeetCode:

Step 1: Create a hash map to count the frequency of each character in the given string.

HashMap<Character, Integer> charFreq = new HashMap<>(); 
for (char c : s.toCharArray()) {
    charFreq.put(c, charFreq.getOrDefault(c, 0) + 1); 
}

This code block creates a hash map called charFreq and loops through each character c in the string s. We use a getOrDefault method to increment the count for a character if it has already been seen before, or initialize it to zero if it's a new character.

Step 2: Sort the hash map by value.

List<Character> chars = new ArrayList<>(charFreq.keySet()); 
Collections.sort(chars, (a, b) -> charFreq.get(b) - charFreq.get(a)); 

Here, we first create a list of all the characters in the hash map using the keySet method. We then sort the characters in the list using a Comparator that compares the frequency of the characters in the hash map.

Step 3: Build the final string by appending the characters in the order of decreasing frequency.

StringBuilder sb = new StringBuilder(); 
for (char c : chars) {
    for (int i = 0; i < charFreq.get(c); i++) {
        sb.append(c); 
    }
}
return sb.toString(); 

This code block uses a StringBuilder to append each character in the list chars in the order of decreasing frequency. We use the get method to get the frequency of each character in the original hash map and loop through it to append the character that many times. Finally, we return the string resulting from the StringBuilder.

Overall, this solution has a time complexity of O(n log n) (for the sorting step) and a space complexity of O(n) (for the hash map and the list of characters).

1