Sort Vowels in a String - Practice Coding Problems

Sort Vowels in a String - Problem

String Sorting Medium

Given a 0-indexed string s, permute s to get a new string t such that:

All consonants remain in their original places. More formally, if there is an index i with 0 <= i < s.length such that s[i] is a consonant, then t[i] = s[i].
The vowels must be sorted in nondecreasing order of their ASCII values. More formally, for pairs of indices i, j with 0 <= i < j < s.length such that s[i] and s[j] are vowels, then t[i] must not have a higher ASCII value than t[j].

Return the resulting string.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in lowercase or uppercase. Consonants comprise all letters that are not vowels.

Input & Output

Example 1 — Basic Vowel Sorting

$ Input: s = "lEetcOde"

› Output: "lEOtcede"

💡 Note: Consonants 'l', 't', 'c', 'd' stay in place. Vowels 'E', 'e', 'O', 'e' are sorted by ASCII: 'E'(69), 'O'(79), 'e'(101), 'e'(101) → 'E', 'O', 'e', 'e'

Example 2 — Mixed Case Vowels

$ Input: s = "lYmpH"

› Output: "lYmpH"

💡 Note: No vowels present in the string, so the string remains unchanged. All characters 'l', 'Y', 'm', 'p', 'H' are consonants.

Example 3 — All Vowels

$ Input: s = "UeAiO"

› Output: "AUOei"

💡 Note: All characters are vowels. Sort by ASCII: 'A'(65), 'O'(79), 'U'(85), 'e'(101), 'i'(105) → 'A', 'U', 'O', 'e', 'i'

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of letters of the English alphabet.
The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in lowercase or uppercase.
Consonants comprise all letters that are not vowels.

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Identify consonants (stay fixed) and vowels (need sorting)

Sort Vowels

Extract vowels and sort by ASCII value

Rebuild String

Place sorted vowels back into vowel positions

Key Takeaway

🎯 Key Insight: Consonants act as anchors while vowels flow to their sorted positions

Asked in

M Microsoft 25 G Google 20 a Amazon 18

The key insight is to keep consonants in place while sorting only the vowels. Extract all vowels from the string, sort them by ASCII value, then place them back into the original vowel positions. Best approach uses extract-sort-replace pattern. Time: O(n log k), Space: O(n) where k is the number of vowels.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Extract, Sort, Replace	O(n log k)	O(n)	Extract all vowels, sort them, then replace vowels in original string with sorted ones
Two-Pass Optimized	O(n log k)	O(n)	First pass extracts vowels, second pass sorts and places them back efficiently

Brute Force - Extract, Sort, Replace — Algorithm Steps

Step 1: Convert string to character array for easy modification
Step 2: Extract all vowels and their positions
Step 3: Sort the extracted vowels by ASCII value
Step 4: Place sorted vowels back into vowel positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Vowels

Find all vowels: ['e', 'E', 'o', 'u']

Sort Vowels

Sort by ASCII: ['E', 'e', 'o', 'u']

Replace Back

Put sorted vowels back in vowel positions

Code -

solution.c — C

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

int isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
           c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}

int compare(const void *a, const void *b) {
    return *(char*)a - *(char*)b;
}

char* solution(char* s) {
    int len = strlen(s);
    char* result = malloc((len + 1) * sizeof(char));
    strcpy(result, s);
    
    // Extract all vowels
    char vowels[len];
    int vowelCount = 0;
    for (int i = 0; i < len; i++) {
        if (isVowel(s[i])) {
            vowels[vowelCount++] = s[i];
        }
    }
    
    // Sort vowels by ASCII value
    qsort(vowels, vowelCount, sizeof(char), compare);
    
    // Replace vowels in original positions with sorted ones
    int vowelIndex = 0;
    for (int i = 0; i < len; i++) {
        if (isVowel(result[i])) {
            result[i] = vowels[vowelIndex++];
        }
    }
    
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log k)

One pass to extract vowels (O(n)), sorting k vowels (O(k log k)), one pass to replace (O(n)), where k ≤ n

⚡ Linearithmic

Space Complexity

O(n)

Character array copy of string (O(n)) plus vowel extraction list (O(k))

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Extract, Sort, Replace — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler