# Sort Characters By Frequency
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sort-characters-by-frequency)
Canonical: https://scaleengineer.com/dsa/problems/sort-characters-by-frequency
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Bucket Sort](https://scaleengineer.com/algorithms/bucket-sort)
**Data structures:** Hash Table, String, Heap (Priority Queue)
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia), [Wipro](https://scaleengineer.com/companies/wipro), [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
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 * 105`
* `s` consists of uppercase and lowercase English letters and digits.

# Approaches
## Sorting with Custom Comparator
This approach involves counting the frequency of each character, then sorting the entire string's characters based on these frequencies using a custom comparator. It's a straightforward but less optimal solution.
**Time:** O(N log N), where N is the length of the string. The dominant operation is sorting the list of N characters. Counting frequencies and building the final string take O(N) time. · **Space:** O(N), for storing the list of N characters to be sorted. The frequency map takes O(K) space where K is the number of unique characters (a small constant).
**Pros:** Relatively straightforward to implement using standard library functions.; The logic is easy to understand.
**Cons:** Less efficient than other approaches due to the O(N log N) sorting complexity.; Requires O(N) extra space for the list of characters, in addition to the space for the frequency map and the output string builder.
### Explanation
First, we iterate through the input string to build a frequency map (e.g., a `HashMap`) that stores each character and its count. Next, we convert the input string into a list of characters. We then sort this list using a custom comparator. The comparator logic is as follows: for any two characters, the one with the higher frequency comes first. The frequencies are looked up from the map. Finally, we join the characters in the sorted list to form the result string. The main bottleneck of this approach is the sorting step, which takes O(N log N) time where N is the length of the string.

```java
import java.util.*;

class Solution {
    public String frequencySort(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }

        // 1. Count character frequencies
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        // 2. Create a list of characters from the string
        List<Character> charList = new ArrayList<>();
        for (char c : s.toCharArray()) {
            charList.add(c);
        }

        // 3. Sort the list with a custom comparator
        Collections.sort(charList, (a, b) -> {
            int freqA = freqMap.get(a);
            int freqB = freqMap.get(b);
            if (freqA != freqB) {
                return freqB - freqA; // Sort by frequency descending
            } else {
                return a - b; // For stable sort, sort lexicographically
            }
        });

        // 4. Build the result string
        StringBuilder sb = new StringBuilder(charList.size());
        for (char c : charList) {
            sb.append(c);
        }

        return sb.toString();
    }
}
```
### Algorithm
*   Create a `HashMap` to store the frequency of each character.
*   Iterate through the input string `s` and populate the frequency map.
*   Convert the string `s` into a `List` of characters.
*   Sort the list using `Collections.sort` with a custom `Comparator`.
*   The comparator should prioritize characters with higher frequency. If frequencies are equal, the relative order can be arbitrary, but a stable sort (e.g., by character value) is good practice.
*   Construct a new string from the sorted list of characters.

## Using a Max Heap (Priority Queue)
This approach uses a max heap (implemented with a `PriorityQueue`) to efficiently retrieve characters with the highest frequency in order. It improves upon the general sorting approach by only sorting the unique characters.
**Time:** O(N + K log K), where N is the length of the string and K is the number of unique characters. O(N) to build the frequency map, and O(K log K) to build and drain the heap. Since K is constant for the given character set (at most 62), the complexity is effectively O(N). · **Space:** O(K), where K is the number of unique characters. This space is for the frequency map and the priority queue. The output `StringBuilder` will take O(N) space.
**Pros:** More efficient than the O(N log N) sorting approach, with a time complexity of O(N + K log K).; Clean implementation using Java's `PriorityQueue`.; Space efficient, as it only needs to store unique characters in the heap.
**Cons:** While having an O(N) time complexity, it might be slightly slower than bucket sort due to the logarithmic factor in heap operations, although K is small.; The implementation is slightly more complex than a simple sort.
### Explanation
First, we build a frequency map of characters, just like in the previous approach. Then, we create a `PriorityQueue` configured as a max heap. The heap will store the character-frequency pairs, and the priority will be determined by their frequency. We add all entries from our frequency map into the heap. The comparator for the heap ensures that entries with higher frequencies have higher priority. After populating the heap, we build the result string. We repeatedly extract the entry with the highest frequency from the heap and append its character to our result `StringBuilder` the corresponding number of times. We continue this process until the heap is empty. This method is more efficient because we only need to maintain the order of K unique characters instead of all N characters.

```java
import java.util.*;

class Solution {
    public String frequencySort(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }

        // 1. Count character frequencies
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        // 2. Create a max heap (PriorityQueue)
        PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue()
        );

        // Add all entries from the map to the heap
        maxHeap.addAll(freqMap.entrySet());

        // 3. Build the result string
        StringBuilder sb = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> entry = maxHeap.poll();
            char character = entry.getKey();
            int frequency = entry.getValue();
            for (int i = 0; i < frequency; i++) {
                sb.append(character);
            }
        }

        return sb.toString();
    }
}
```
### Algorithm
*   Create a `HashMap` to store the frequency of each character.
*   Iterate through the input string `s` and populate the frequency map.
*   Create a `PriorityQueue` (max heap) that orders elements by frequency in descending order.
*   Add all character-frequency pairs (e.g., `Map.Entry`) from the map into the max heap.
*   Initialize an empty `StringBuilder`.
*   While the heap is not empty, poll the entry with the highest frequency.
*   Append the character from the polled entry to the `StringBuilder` a number of times equal to its frequency.
*   Return the string from the `StringBuilder`.

## Bucket Sort
This is the most efficient approach, utilizing the concept of bucket sort to achieve linear time complexity. It avoids comparison-based sorting by grouping characters directly by their frequency.
**Time:** O(N), where N is the length of the string. Counting frequencies is O(N), populating buckets is O(K) (where K is the number of unique characters, K <= N), and building the final string is O(N). · **Space:** O(N), where N is the length of the string. This is required for the `buckets` array. The frequency map takes O(K) space, and the output `StringBuilder` takes O(N) space.
**Pros:** Most efficient solution with a linear time complexity of O(N).; Avoids comparison-based sorting and its associated overhead.
**Cons:** Uses more space for the `buckets` array, which can be up to `N+1` in size, where N is the string length.
### Explanation
The core idea is to use an array as 'buckets,' where the index of the array represents a character frequency. First, we compute the frequency of each character in the input string. Next, we create an array of lists, `buckets`, of size `s.length() + 1`. `buckets[i]` will store all characters that appear `i` times in the string. We then iterate through our frequency map. For each character `c` with frequency `f`, we add `c` to the list at `buckets[f]`. Finally, we construct the result string. We iterate through the `buckets` array from the highest possible frequency (`s.length()`) down to 1. For each frequency `i`, we get the list of characters from `buckets[i]`. For each character in this list, we append it to our result `StringBuilder` `i` times. This avoids any comparison-based sorting, leading to a true linear time solution.

```java
import java.util.*;

class Solution {
    public String frequencySort(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }

        // 1. Count character frequencies
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        // 2. Create buckets for frequencies
        // The max frequency can be s.length()
        List<Character>[] buckets = new List[s.length() + 1];

        // 3. Populate buckets
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            char character = entry.getKey();
            int frequency = entry.getValue();
            if (buckets[frequency] == null) {
                buckets[frequency] = new ArrayList<>();
            }
            buckets[frequency].add(character);
        }

        // 4. Build the result string from buckets
        StringBuilder sb = new StringBuilder();
        for (int i = buckets.length - 1; i >= 1; i--) {
            if (buckets[i] != null) {
                for (char character : buckets[i]) {
                    for (int j = 0; j < i; j++) {
                        sb.append(character);
                    }
                }
            }
        }

        return sb.toString();
    }
}
```
### Algorithm
*   Create a frequency map (or an array of size 128 for ASCII) for the characters in the string `s`.
*   Create an array of lists, `buckets`, of size `s.length() + 1`. The index `i` will correspond to frequency `i`.
*   Iterate through the frequency map. For each character `c` with frequency `f`, add `c` to the list at `buckets[f]`.
*   Initialize an empty `StringBuilder`.
*   Iterate through the `buckets` array from the last index (`s.length()`) down to 1.
*   If `buckets[i]` is not empty, iterate through the characters in it. For each character, append it to the `StringBuilder` `i` times.
*   Return the resulting string.

# Solutions
### Java

```java
class Solution { public String frequencySort ( String s ) { Map < Character , Integer > cnt = new HashMap <>( 52 ); for ( int i = 0 ; i < s . length (); ++ i ) { cnt . merge ( s . charAt ( i ), 1 , Integer: : sum ); } List < Character > cs = new ArrayList <>( cnt . keySet ()); cs . sort (( a , b ) -> cnt . get ( b ) - cnt . get ( a )); StringBuilder ans = new StringBuilder (); for ( char c : cs ) { for ( int v = cnt . get ( c ); v > 0 ; -- v ) { ans . append ( c ); } } return ans . toString (); } }
```

### CPP

```cpp
class Solution { public: string frequencySort ( string s ) { unordered_map < char , int > cnt ; for ( char & c : s ) { ++ cnt [ c ]; } vector < char > cs ; for ( auto & [ c , _ ] : cnt ) { cs . push_back ( c ); } sort ( cs . begin (), cs . end (), [ & ]( char & a , char & b ) { return cnt [ a ] > cnt [ b ]; }); string ans ; for ( char & c : cs ) { ans += string ( cnt [ c ], c ); } return ans ; } };
```

### Python

```python
class Solution : def frequencySort ( self , s : str ) -> str : cnt = Counter ( s ) return '' . join ( c * v for c , v in sorted ( cnt . items (), key = lambda x : - x [ 1 ]))
```