LeetCode Daily Problem P2785 Sort Vowels in a String

---

Timeline

timeline

2025-09-11

init

counting sort

---

Problem:

P2785Sort 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. The algorithm complexity is 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 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., open an array of the size of the interval of numbers to be sorted, put the numbers to be sorted into the array elements at corresponding indices for counting, then accumulate the sum to find how many numbers are before each number, thus directly determining the position of this number in the sorted array. The algorithm 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, those not equal to -1 are vowels.
                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