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

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