6ms C solution


  • 0
    V

    Use 2 arrays:

    • Array A contains characters to numbers of occurrences.
    • Array B contains distinct characters

    Sort characters in B by looking up its number of occurrence in A, then iterate B to make a new string by repeating each character A[c] times.

    int cmpLetters(const void* a, const void* b);
    
    int times[256];
    
    char* frequencySort(char* s)
    {
        char letters[256];
        int i, j, k, lnum;
    
        // Init occurrences as 0
        memset(times, 0, sizeof(times));
    
        for (i = lnum = 0; s[i] != '\0'; i++)
            if (times[s[i]]++ == 0)
                letters[lnum++] = s[i];
    
        // Sort letters by number of occurrences
        qsort(letters, lnum, sizeof(char), cmpLetters);
    
        char* new = malloc(sizeof(char) * (i + 1));
    
        for (j = k = 0; j < lnum; j++)
            for (i = 0; i < times[letters[j]]; i++)
                new[k++] = letters[j];
        new[k] = '\0';
    
        return new;
    }
    
    int cmpLetters(const void* a, const void* b)
    {
        return times[*(char*)b] - times[*(char*)a];
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.