tags: leetcode medium Hash Table String Sort Heap(Priority Queue) Bucket Sort Counting

451. 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;
    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