Problem 31 - Sort Characters By Frequency

Explore our archive for previous posts.

Problem 30 - Merge Intervals

Problem 29 - Min Cost Climbing Stairs

Question

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example 1:

Input: s = "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: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "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.

Constraints:

• 1 <= s.length <= 5 * 10^5

• s consists of uppercase and lowercase English letters and digits.

Approach

The approach involves creating a frequency map to count the occurrences of each character in the given string. Then, a max heap (priority queue) is used to sort characters based on their frequencies in descending order. Finally, a sorted string is built by repeatedly extracting characters with the highest frequency from the max heap and appending them to the string.

Here are the detailed steps:

1. Create a frequency map using a HashMap to count the occurrences of each character in the string.

2. Construct a max heap (priority queue) using a custom comparator that sorts characters based on their frequencies in descending order. This way, characters with higher frequencies will be at the top of the heap.

3. Add characters from the frequency map to the max heap.

4. Build the sorted string by extracting characters with the highest frequency from the max heap and appending them to the string. Repeat this process until the heap is empty.

5. Return the sorted string.

Solution

Solve it here

class Solution {
    public String frequencySort(String s) {
        // Create a map to store character frequencies
        Map<Character, Integer> frequencyMap = new HashMap<>();
        
        // Count character frequencies
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }
        
        // Create a max heap (priority queue) based on character frequencies
        PriorityQueue<Character> maxHeap = new PriorityQueue<>((a, b) -> frequencyMap.get(b) - frequencyMap.get(a));
        
        // Add characters to the max heap
        maxHeap.addAll(frequencyMap.keySet());
        
        // Build the sorted string
        StringBuilder sortedString = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            char c = maxHeap.poll();
            int frequency = frequencyMap.get(c);
            for (int i = 0; i < frequency; i++) {
                sortedString.append(c);
            }
        }
        
        return sortedString.toString();
    }
}

Time and space complexity

Time Complexity: The time complexity is O(n log n), where 'n' is the length of the input string. Building the max heap takes O(n log n) time. The max heap can have at most 'n' elements, and each insertion takes O(log n) time. Building the sorted string also takes O(n log n) time. In the worst case, we extract each character from the max heap and append it to the string, which takes O(log n) time for each character.

Space Complexity: The space complexity is O(n) due to the space used by the frequency map and the max heap. The frequencyMap takes O(k) space, where 'k' is the number of unique characters in the input. In the worst case, 'k' could be the length of the entire alphabet (26 for English letters). The max heap uses O(n) space since it can store at most 'n' characters.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!