LeetCode daily problem P2785 Sort Vowels in a String

---

Timeline

Timeline

2025-09-11

init

Counting sort

---

Problem:

P2785Sort the vowels in a string

https://leetcode.cn/problems/sort-vowels-in-a-string/description/?envType=daily-question&envId=2025-09-11

I use the method of extracting first, then sorting, and finally overwriting, with a time complexity of O(n log n)

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool isVowel(char c)
{
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' ||
            c == 'I' || c == 'O' || c == 'U') {
                return true;
        }
        return false;
}
// increasing
int comparefunc(const void *a, const void *b)
{
        return *(char *)a - *(char *)b;
}
char *sortVowels(char *s)
{
        int len;
        int vowel_count = 0;
        char *str, *vowels;
        int index = 0;

        len = strlen(s);
        // Note that you need to copy len + 1 bytes
        str = malloc((len + 1) * sizeof(char));
        strcpy(str, s);

        for (int i = 0; i < len; i++) {
                if (isVowel(str[i])) {
                        vowel_count++;
                }
        }
        vowels = (char *)malloc(vowel_count * sizeof(char));
        for (int i = 0; i < len && index < vowel_count; i++) {
                if (isVowel(str[i])) {
                        vowels[index] = str[i];
                        index++;
                }
        }
        qsort(vowels, vowel_count, sizeof(char), comparefunc);
        index = 0;
        for (int i = 0; i < len && index < vowel_count; i++) {
                if (isVowel(str[i])) {
                        str[i] = vowels[index];
                        index++;
                }
        }
        free(vowels);
        return str;
}

int main()
{
        // Constant strings cannot be modified
        char *s = "lEetcOde";
        char *str;
        str = sortVowels(s);
        printf("%s\n", str);
        free(str);
}

Recommended method: use the idea of counting sort, i.e., allocate an array of the size of the range of the numbers to be sorted, place the numbers to be sorted into the array elements at the corresponding indices for counting, then use the cumulative sum to find how many numbers come before each number, thereby directly determining the position of this number in the sorted array. The time complexity is O(n).

ASCIIcode table

https://www.runoob.com/w3cnote/ascii.html

char *sortVowels(char *s)
{
        const char vowels[] = { 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U' };
        int cnt[58];
        for (int i = 0; i < 58; i++) {
                cnt[i] = -1;
        }
        for (int i = 0; i < 10; i++) {
                int idx = vowels[i] - 'A';
                cnt[idx] = 0;
        }

        int len = strlen(s);
        for (int i = 0; i < len; i++) { // In the cnt array, the entries that are not -1 are the vowel letters
                int idx = s[i] - 'A';
                if (cnt[idx] != -1) {
                        cnt[idx]++;
                }
        }

        char *res = (char *)malloc(len + 1);
        strcpy(res, s);
        int idx = 0;
        for (int i = 0; i < len; i++) {
                int pos = res[i] - 'A';
                if (cnt[pos] != -1) { //If it is a vowel letter
                        while (cnt[idx] <= 0) {
                                idx++; //Find the next vowel letter
                        }
                        res[i] = idx + 'A';
                        cnt[idx]--;
                }
        }

        return res;
}

Counting sort

https://www.runoob.com/w3cnote/counting-sort.html