Skip to main content

Hashing

Sort Characters By Frequency Solution In C++/Java/Python/Javascript

Problem Description

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

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.

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.

Constraints

  • 1 <= s.length <= 5 * 10^5
  • s consists of uppercase and lowercase English letters and digits.
💡
Try it Yourself First
To sort characters by frequency, count occurrences, then prioritize the most frequent ones and construct the result efficiently.

Brute Force Approach

Intuition

To sort characters by frequency, our goal is to rearrange the characters so that those with the highest frequencies come first. for this ,we need to handle two main tasks:

First, we need to count how often each character appears in the string. This gives us the frequency data. we need to understand which characters are the most common. To count how often each character appears in the string, we use a frequency map. This is typically done using a data structure like a hash map (or unordered map in C++). A hash map allows us to efficiently store and retrieve the frequency of each character as we scan through the string
Why Use a Hash Map?
Efficiency: Hash maps provide an average time complexity of O(1) for insertions and lookups. This means that counting the frequencies of all characters in the string is very fast.
Simplicity: Using a hash map simplifies the code and makes it easier to understand and maintain.

Next, to efficiently get the characters in order of their frequency, we use a Max Heap. A Max Heap allows us to always get the character with the highest frequency quickly without having to sort the entire list of frequencies. It’s like having a system that automatically prioritizes the most frequent characters for us.
With the Max Heap, we can repeatedly extract the character with the highest frequency and add it to our result string the number of times it appears. This process ensures that the characters are ordered by their frequency from highest to lowest in our final string.
By using the Max Heap, we make the solution faster and cleaner, allowing us to achieve the desired ordering efficiently.

Approach

Step 1: Create Frequency Map
We start by creating a frequency map (freq) to count how many times each character (c) appears in the input string (s). This is crucial because we need to identify which characters appear most frequently. For each character in the string, we increment its count in our frequency map, giving us a clear picture of character distributions.

Step 2: Use a Max Heap (Priority Queue)
After counting frequencies, we use a max heap (priority queue) to store characters based on their frequency. This allows us to efficiently retrieve the character with the highest frequency. We push each character (c) and its frequency (f) as a pair into the max heap (pq).

Step 3: Build the Result String
We initialize an empty result string (result). We then repeatedly extract the character with the highest frequency from the max heap, appending it to the result string as many times as its frequency. This step ensures that characters are added to the result string in the order of their frequencies, from highest to lowest.

Step 4: Generate the Sorted String
Once the max heap is empty, the result string is complete. This string contains characters sorted by their frequencies in descending order. We return the result string (result) as the final output

Dry Run

  • Input: s = "cccaaa"
  • Step 1: Build Frequency Map
  • Scan string left to right:
    c -> seen 3 times
    a -> seen 3 times
    Frequency map: {c:3, a:3}
  • Step 2: Build Max Heap
    Push (frequency, char) pairs:
    Push (3,'c')
    Push (3,'a')
    Heap now contains: (3,'c'), (3,'a')
    Note: Both have same frequency, either can be at top
  • Step 3: Build Result String
    Initialize: result = ""
    First extraction:
    - Pop (3,'c')
    - Append 'c' three times
    - result = "ccc"
    Second extraction:
    - Pop (3,'a')
    - Append 'a' three times
    - result = "cccaaa"
    Heap is empty, we're done!
  • Output: "cccaaa"
  • Additional examples:
    Input: s = "tree"
  • Step 1: Frequency Map
    e -> 2
    t -> 1
    r -> 1
  • Step 2: Max Heap
    Push (2,'e'), (1,'t'), (1,'r')
  • Step 3: Build String
    Pop (2,'e') -> "ee"
    Pop (1,'t') -> "eet"
    Pop (1,'r') -> "eet
  • Why this works:
    1. HashMap ensures accurate frequency count
    2. Priority Queue automatically sorts by frequency
    3. When frequencies are equal, character order doesn't matter
    4. We append each character exactly its frequency times
Code for All Languages
C++ 
// Approach: Sort Characters By Frequency using HashMap and Priority Queue  
// Language: C++  

class Solution {  
public:  
    // Function to sort characters by frequency using HashMap and Priority Queue  
    // Time Complexity: O(n + k log k), where n is the length of the string and k is the number of unique characters  
    // Space Complexity: O(n + k)  
    string frequencySort(string s) {  
        // Step 1: Count the frequency of each character using an unordered_map  
        unordered_map<char, int> freq;  
        for (char c : s) {  
            freq[c]++;  
        }  

        // Step 2: Use a max heap (priority queue) to store characters by their frequency  
        priority_queue<pair<int, char>> pq;  
        for (const auto& [c, f] : freq) {  
            pq.push({f, c});  // Push frequency and character as a pair  
        }  

        // Step 3: Build the result string by appending characters based on their frequency  
        string result;  
        while (!pq.empty()) {  
            // Get the character with the highest frequency  
            auto [f, c] = pq.top();  
            pq.pop();  
            
            // Append 'f' occurrences of character 'c'  
            result.append(f, c);  
        }  

        // Return the sorted string  
        return result;  
    }  
};

Java 
// Approach: Sort Characters By Frequency using HashMap and Priority Queue  
// Language: Java  

// This program sorts characters in a string based on their frequency.  
// It uses a HashMap to count character frequencies and a max heap to sort them.  

class Solution {  
    // Function to sort characters by frequency using HashMap and Priority Queue  
    // Time Complexity: O(n + k log k), where n is the length of the string and k is the number of unique characters  
    // Space Complexity: O(n + k)  
    public String frequencySort(String s) {  
        // Step 1: Count the frequency of each character using a HashMap  
        Map<Character, Integer> freq = new HashMap<>();  
        for (char c : s.toCharArray()) {  
            freq.put(c, freq.getOrDefault(c, 0) + 1);  
        }  

        // Step 2: Use a max heap (priority queue) to store characters by their frequency  
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(  
            (a, b) -> b.getValue() - a.getValue()  
        );  
        pq.addAll(freq.entrySet());  

        // Step 3: Build the result string by appending characters based on their frequency  
        StringBuilder result = new StringBuilder();  
        while (!pq.isEmpty()) {  
            Map.Entry<Character, Integer> entry = pq.poll();  
            char c = entry.getKey();  
            int f = entry.getValue();  
            for (int i = 0; i < f; i++) {  
                result.append(c);  
            }  
        }  

        // Return the sorted string  
        return result.toString();  
    }  
}

Python 
# Approach: Sort Characters By Frequency using Dictionary and Priority Queue  
# Language: Python  

# This program sorts characters in a string based on their frequency.  
# It uses a dictionary to count character frequencies and a max heap to sort them.  

import heapq  
from collections import defaultdict  

class Solution(object):  
    # Function to sort characters by frequency using Dictionary and Priority Queue  
    # Time Complexity: O(n + k log k), where n is the length of the string and k is the number of unique characters  
    # Space Complexity: O(n + k)  
    def frequencySort(self, s):  
        """  
        :type s: str  
        :rtype: str  
        """  
        # Step 1: Count the frequency of each character using a dictionary  
        freq = defaultdict(int)  
        for c in s:  
            freq[c] += 1  

        # Step 2: Use a max heap (priority queue) to store characters by their frequency  
        pq = [(-f, c) for c, f in freq.items()]  
        heapq.heapify(pq)  

        # Step 3: Build the result string by appending characters based on their frequency  
        result = []  
        while pq:  
            f, c = heapq.heappop(pq)  
            result.extend(c * (-f))  

        # Return the sorted string  
        return ''.join(result)

Javascript 
/**
 * Approach: Sort Characters By Frequency Using Max Heap (Priority Queue)
 * Language: JavaScript
 *
 * @param {string} s - Input string containing characters.
 * @return {string} - String sorted by character frequency in descending order.
 */
var frequencySort = function(s) {
    // Step 1: Count the frequency of each character using a Map
    const freq = new Map();
    for (const c of s) {
        freq.set(c, (freq.get(c) || 0) + 1);
    }

    // Step 2: Use a max heap (priority queue) to store characters sorted by frequency
    const pq = new MaxPriorityQueue({ priority: x => x[0] });
    for (const [c, f] of freq) {
        pq.enqueue([f, c]);
    }

    // Step 3: Build the result string by appending characters based on their frequency
    let result = '';
    while (!pq.isEmpty()) {
        const [f, c] = pq.dequeue().element;
        result += c.repeat(f);
    }

    return result; // Return the sorted string
};

Time Complexity: O(n + k log k)

  • String Traversal and Counting
    Initial string traversal: O(n)
    Each map insertion: O(1)
    Total counting phase: O(n)
  • Priority Queue Operations
    Building heap with k unique chars: O(k)
    Each push operation: O(log k)
    Total heap construction: O(k log k)
  • Result String Construction
    At most k pop operations
    Each pop: O(log k)
    String appending: O(n) total
    Total construction: O(k log k + n)
  • Overall Time Complexity O(n + k log k), where: n is string length
    k is number of unique characters (≤ 128 for ASCII)

Space Complexity : O(k+n)

  • Auxiliary Space Breakdown
    Frequency map: O(k)
    Priority queue: O(k)
    Result string: O(n)
  • Total auxiliary space: O(n + k)
  • Best/Worst Cases
    Best case: k = 1 (all same characters)
    Worst case: k = n (all unique characters)
    In practice, k ≤ 128 for ASCII characters
    Total Space Requirements
    Input string: O(n)
    Additional structures: O(n + k)
  • Final space complexity: O(n + k)
In the Priority Queue approach, we found inefficiencies like extra space usage and the complexity of managing the queue. To improve, we switched to using just a HashMap and sorting the string in-place. This simplified the implementation, reduced space complexity, and made the solution more efficient, achieving the same result with fewer steps.

Optimal Approach

Intuition

Let’s dive straight into the intuition for sorting characters by frequency using an optimal approach.
First, we need to count how often each character appears in the string. To do this, we use a frequency array because it’s efficient and provides O(1) lookup times. We’re assuming a fixed ASCII range, which makes this approach suitable for our needs.
Once we have the frequencies, we face the challenge of ordering the characters by their frequency. You might wonder, why not just sort the characters? Well, sorting by frequency involves more than just a simple sort, so we use a custom sorting method.
Here’s where the fun begins. We create a new string that’s a copy of the input and then sort this string based on two criteria:
 — Characters with higher frequencies should come first.
 — If two characters have the same frequency, they should be ordered lexicographically (i.e., based on their ASCII values).
To achieve this, we use the sort function with a custom comparator. The comparator ensures that characters are sorted first by frequency and, if frequencies are equal, by their character value.
By following these steps, we efficiently generate a sorted string where characters are ordered by their frequencies in descending order. This approach is both fast and simple, leveraging the efficiency of the frequency array and the power of custom sorting.

Approach

Step 1: Count the Frequency of Each Character
We start by creating a frequency array (freq) to count how many times each character appears in the input string (s). This frequency array will have a fixed size of 128, assuming ASCII characters. For each character © in the string, we increment its count in our frequency array. This gives us a clear distribution of character frequencies.

Step 2: Sort the String Based on Frequency and Character Order
After counting the frequencies, we create a new string (sorted_string) which is a copy of the input string (s). We then sort this string based on two criteria:
 - Characters with higher frequencies should come first.
 - If two characters have the same frequency, they should be ordered lexicographically (i.e., based on their ASCII values).
We achieve this sorting by using the sort function with a custom comparator.

Step 3: Generate the Sorted String
After sorting the string based on frequency and character order, the result string (sorted_string) contains characters in the desired order. This string is then returned as the final output.

Dry Run

  • Input: s = "tree"
  • Step 1: Count Frequencies
    Create frequency array (size 128 for ASCII):
    t -> freq[116] = 1
    r -> freq[114] = 1
    e -> freq[101] = 2
  • Step 2: Custom Sorting
    Original string: "tree"
    Compare adjacent characters:
    't' vs 'r':
    - freq[t] = 1, freq[r] = 1
    - Same frequency, compare chars: 't' > 'r'
    - Swap: "rtee"
    'r' vs 'e':
    - freq[r] = 1, freq[e] = 2
    - 1 < 2, keep moving 'e' left
    - Result: "etre"
    Continue sorting:
  • Final result: "eert"
  • Why this approach works:
    1. Frequency array gives O(1) lookup for frequencies
    2. Custom comparator ensures:
    - Higher frequencies come first
    - Same characters stay together
    3. Sort maintains stable ordering for equal frequencies
Code for All Languages
C++ 
// Approach: Sort Characters By Frequency using HashMap and Sorting
// Language: C++

// This program sorts characters in a string based on their frequency.  
// It uses a frequency array (assuming ASCII characters) and sorting.  

class Solution {  
public:  
    // Function to sort characters by frequency using HashMap and Sorting  
    // Time Complexity: O(n log n), where n is the length of the string  
    // Space Complexity: O(1), assuming fixed ASCII range  
    string frequencySort(string s) {  
        // Step 1: Count the frequency of each character (assuming ASCII characters)  
        vector<int> freq(128, 0); // Frequency array for ASCII characters  
        for (char c : s) {  
            freq[c]++;  
        }  

        // Step 2: Sort the string based on frequency and character order  
        sort(s.begin(), s.end(), [&](char a, char b) {  
            return freq[a] > freq[b] || (freq[a] == freq[b] && a < b);  
        });  

        // Return the sorted string  
        return s;  
    }  
};

Java 
// Approach: Sort Characters By Frequency using HashMap and Sorting
// Language: Java

// This program sorts characters in a string based on their frequency.  
// It uses a frequency array (assuming ASCII characters) and sorting.  

class Solution {
    // Function to sort characters by frequency using HashMap and Sorting  
    // Time Complexity: O(n log n), where n is the length of the string  
    // Space Complexity: O(1), assuming fixed ASCII range  
    public String frequencySort(String s) {
        // Step 1: Count the frequency of each character (assuming ASCII characters)  
        int[] freq = new int[128]; // Frequency array for all ASCII characters  
        for (char c : s.toCharArray()) {
            freq[c]++;
        }

        // Step 2: Sort the string based on frequency and character order  
        Character[] chars = new Character[s.length()];
        for (int i = 0; i < s.length(); i++) {
            chars[i] = s.charAt(i);
        }

        Arrays.sort(chars, (a, b) -> freq[a] != freq[b] ? freq[b] - freq[a] : a - b);

        // Step 3: Build the result string  
        StringBuilder result = new StringBuilder(chars.length);
        for (char c : chars) {
            result.append(c);
        }

        // Return the sorted string  
        return result.toString();
    }
}

Python 
# Approach: Sort Characters By Frequency using Dictionary and Sorting  
# Language: Python  

# This program sorts characters in a string based on their frequency.  
# It uses a frequency array (assuming ASCII characters) and sorting.  

class Solution(object):  
    # Function to sort characters by frequency using Dictionary and Sorting  
    # Time Complexity: O(n log n), where n is the length of the string  
    # Space Complexity: O(1) assuming fixed ASCII range  
    def frequencySort(self, s):  
        """  
        :type s: str  
        :rtype: str  
        """  
        # Step 1: Count the frequency of each character (assuming ASCII characters)  
        freq = [0] * 128  # Frequency array for all ASCII characters  
        for c in s:  
            freq[ord(c)] += 1  

        # Step 2: Sort the string based on frequency and character order  
        sorted_chars = sorted(s, key=lambda x: (-freq[ord(x)], x))  

        # Return the sorted string  
        return ''.join(sorted_chars)

Javascript 
/**
 * Approach: Sort Characters By Frequency using HashMap and Sorting
 * Language: JavaScript
 *
 * @param {string} s - Input string containing characters.
 * @return {string} - String sorted by character frequency in descending order.
 */
function frequencySort(s) {
    // Step 1: Count the frequency of each character (assuming ASCII characters)
    let freq = new Map();
    for (let c of s) {
        freq.set(c, (freq.get(c) || 0) + 1);
    }

    // Step 2: Sort the characters by frequency and lexicographical order
    let sortedChars = [...s].sort((a, b) => {
        return freq.get(b) - freq.get(a) || a.localeCompare(b);
    });

    // Return the sorted string
    return sortedChars.join("");
}

Time Complexity: O(n log n)

  • Frequency Counting
    Single pass through string: O(n)
    Array access for counting: O(1)
  • Total counting phase: O(n)
  • String Sorting
    sort complexity: O(n log n)
    Comparator function calls: O(1)
  • Total sorting phase: O(n log n)
  • Overall Time Complexity O(n log n), where: n is string length dominated by sorting operation
    Comparator function is O(1)

Space Complexity : O(n)

  • Auxiliary Space Breakdown
    Frequency array: O(1) fixed 128 size
    Sorted string copy: O(n)
    Sort algorithm space: O(log n) typically
  • Total auxiliary space: O(n)
  • Best/Worst Cases
    Best case: Still O(n log n)
    Worst case: O(n log n)
    Space always O(n) due to string copy
  • Total Space Requirements
    Input string: O(n)
    Frequency array: O(1)
    Result string: O(n)
  • Final space complexity: O(n)
  • Note: While we use O(1) for the frequency array since it’s fixed size (128), some might argue it should be included in the space complexity notation. However, since it’s independent of input size, we consider it constant.

Learning Tip

Now we have successfully tackled this problem, let’s try these similar problems.

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

K Frequent ElementsFirst Unique Character in a String

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.