Sort Vowels in a String — Medium Problem & Solution

Problem statement

Rearrange s so that:

• every consonant stays exactly where it was, and
• the vowels — a, e, i, o, u in either case — are sorted into non-decreasing ASCII order among the positions they already occupy.

Return the resulting string. Note that all uppercase letters sort before all lowercase ones.

Example 1

Input: s = "codekairo"
Output: cadekioro
Explanation: The vowels `o,e,a,i,o` sort to `a,e,i,o,o` and refill positions 1, 3, 5, 6 and 8.

Example 2

Input: s = "lEetcOde"
Output: lEOtcede
Explanation: `E` (69) and `O` (79) come before the two lowercase `e`s (101).

Example 3

Input: s = "lYmpH"
Output: lYmpH
Explanation: No vowels, so nothing moves.

Constraints

• 1 <= s.length <= 10^5
• s consists only of letters of the English alphabet in uppercase and lowercase.

How to solve Sort Vowels in a String

Extract the vowels, sort them, and write them back into the same positions left to right. Consonants are copied through untouched.

Approach

1. Scan s, collecting every vowel into a list.
2. Sort the list by character code.
3. Rebuild the string: at a vowel position emit the next sorted vowel, otherwise the original character.

Why it works

The positions of the vowels never change — only which vowel sits in each — so the problem separates cleanly into "which slots" and "what order". With only ten possible vowel characters, tallying them and emitting in code order beats a comparison sort and makes the whole thing O(n).

Complexity

• Time — O(n log n), or O(n) with a counting sort
• Space — O(n)

Pitfalls

• The order is by ASCII, so every uppercase vowel precedes every lowercase one — not case-insensitive alphabetical.
• Consonants must not shift; only the vowel slots are refilled.
• y is not a vowel here.

Reference solution

Python

def sortVowels(s: str) -> str:
    vowels = sorted(c for c in s if c in "aeiouAEIOU")
    it = iter(vowels)
    return "".join(next(it) if c in "aeiouAEIOU" else c for c in s)

JavaScript

var sortVowels = function(s) {
    var V = "aeiouAEIOU";
    var vowels = [], i;
    for (i = 0; i < s.length; i++) {
        if (V.indexOf(s.charAt(i)) !== -1) vowels.push(s.charAt(i));
    }
    vowels.sort();
    var out = "", k = 0;
    for (i = 0; i < s.length; i++) {
        out += V.indexOf(s.charAt(i)) !== -1 ? vowels[k++] : s.charAt(i);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium