---
# System prepended metadata

title: '[451. Sort Characters By Frequency](https://leetcode.com/problems/sort-characters-by-frequency/)'
tags: [Hash Table, Heap(Priority Queue), medium, String, Counting, leetcode, Bucket Sort, Sort]

---

###### tags: `leetcode` `medium` `Hash Table` `String` `Sort` `Heap(Priority Queue)` `Bucket Sort` `Counting`
# [451. Sort Characters By Frequency](https://leetcode.com/problems/sort-characters-by-frequency/)

## 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*.  

## Examples
### 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 \leq s.length \leq 5 \times 10^5$  
- `s` consists of uppercase and lowercase English letters and digits.  

## Code

```c=
typedef struct alph{
    char c;
    int freq;
}ALPH;

int cmp(const void * a, const void * b){
    return ((ALPH*)b)->freq - ((ALPH*)a)->freq;
}

char * frequencySort(char * s){
    ALPH count[62] = {{'0', 0}};
    char *result = calloc(strlen(s) + 1, sizeof(char));
    // Initialize
    for(int i = 0 ; i < 26 ; i++)
        count[i].c = i + 'A';
    for(int i = 26 ; i < 52 ; i++)
        count[i].c = i + 'a' - 26;
    for(int i = 52 ; i < 62 ; i++)
        count[i].c = i + '0' - 52;
    // Count frequency
    while(*s != '\0'){
        if(*s >= 'a')
            count[*s++ - 'a' + 26].freq++;
        else if(*s >= 'A')
            count[*s++ - 'A'].freq++;
        else
            count[*s++ - '0' + 52].freq++;
    }
    // Sort alpabetics by frequency
    qsort(count, 62, sizeof(ALPH), cmp);
    // Assign character by frequency
    char *tmp = result;
    for(int i = 0 ; i < 62 ; i++){
        for(int j = 0 ; j < count[i].freq ; j++)
            *tmp++ = count[i].c;
    }
    result[strlen(result)] = '\0';
    return result;
}
```

## Complexity

|Space |Time        |
|-     |-           |
|$O(1)$|$O(Nlog(N))$|

## Result

- Runtime: 7 ms, faster than 67.21%  
- Memory Usage: 6.8 MB, less than 26.23%  

## Notes

- ASCII code:  
    - 0 : 43  
    - A : 65  
    - a : 97  