Sort Vowels in a String — Extract, Sort, Reinsert Cleanly

Problem Statement#

Given a 0-indexed string s, permute s so that consonants stay in place and vowels are sorted in non-decreasing ASCII order. Vowels are a, e, i, o, u and their uppercase variants.

Constraints:

• 1 <= s.length <= 10^5
• s contains English letters only.

Input:  s = "lEetcOde"
Output: "lEOtcede"

Input:  s = "lYmpH"
Output: "lYmpH"

Why This Problem Matters#

LeetCode 2785 — Sort Vowels in a String — is a Medium that Amazon and Microsoft use as a screen-friendly warm-up before harder string manipulation problems. It tests whether you can operate on a subset of elements while leaving the rest untouched, a pattern that shows up in UI rendering, partial database updates, and structured text editing.

The hidden difficulty is ASCII ordering: uppercase letters come before lowercase ('E' = 69 < 'e' = 101). Candidates who lowercase before sorting silently break the test cases. Interviewers often follow up with "now sort by frequency" or "sort consonants too", so understanding the extract-sort-reinsert template matters more than producing a one-liner.

This blog teaches the cleanest implementation, the counting-sort optimisation that drops to O(n), and the most common interview follow-ups so you can answer them confidently.

The Core Insight#

Three steps solve the problem with no special cases:

1. Walk left to right and collect all vowels into a list.
2. Sort that list by ASCII value (Python's default character sort is exactly ASCII).
3. Walk left to right again. At every vowel position, drop in the next sorted vowel.

Because both walks visit positions in left-to-right order, the sorted vowels slot perfectly into the holes vacated by the originals. Two-pointer swap-from-the-ends gives a reversal, not a sort, so it cannot replace this pattern.

For an O(n) version, run counting sort over the 10 distinct vowel characters: count each vowel, then sweep the 10 buckets in ASCII order to refill positions. The asymptotic improvement is rarely required by interviewers but earns bonus credit when offered.

Visual Dry Run#

s = "lEetcOde". Vowels collected left-to-right: ['E', 'e', 'O', 'e']. Sorted by ASCII: ['E', 'O', 'e', 'e'].

Final: "lEOtcede".

Solution (Optimal)#

class Solution:
    def sortVowels(self, s):
        VOWELS = set('aeiouAEIOU')
 
        # Step 1: collect vowels left to right.
        vowels = [c for c in s if c in VOWELS]
 
        # Step 2: ASCII-order sort. Python's default char sort is ASCII.
        vowels.sort()
 
        # Step 3: rebuild, replacing each vowel slot with the next sorted vowel.
        result = list(s)
        vi = 0
        for i, c in enumerate(result):
            if c in VOWELS:
                result[i] = vowels[vi]
                vi += 1
 
        return ''.join(result)

var sortVowels = function(s) {
    const VOWELS = new Set(['a','e','i','o','u','A','E','I','O','U']);
 
    const vowels = [];
    for (const c of s) {
        if (VOWELS.has(c)) vowels.push(c);
    }
 
    vowels.sort((a, b) => a.charCodeAt(0) - b.charCodeAt(0));
 
    const result = s.split('');
    let vi = 0;
    for (let i = 0; i < result.length; i++) {
        if (VOWELS.has(result[i])) {
            result[i] = vowels[vi++];
        }
    }
 
    return result.join('');
};

Time: O(n log n) for the comparison sort, or O(n) with counting sort over 10 buckets. Space: O(n) for the vowel list and the mutable string copy.

Common Mistakes#

• Lowercasing before sorting, which loses the required ASCII ordering between cases.
• Treating Y as a vowel; the problem allows only aeiouAEIOU.
• Mutating a Python string directly; convert to a list first.
• Using two-pointer swap from both ends, which reverses rather than sorts.
• Building set('aeiou') only and missing the uppercase variants.

Interview Tips#

• State the three-step plan before coding so the interviewer can interrupt with constraints.
• Mention the ASCII subtlety: 'A' < 'Z' < 'a', so case matters.
• Volunteer the counting-sort O(n) variant after the comparison-sort version.
• Confirm vowel definition with the interviewer because some variants include Y.

Follow-up Questions#

• Sort consonants too? Run the same template twice with different membership tests.
• Sort vowels by frequency? Sort the bucket by (-count, ascii).
• Sort in-place without an auxiliary list? Use counting sort with 10 fixed buckets.
• Unicode input? Swap the membership predicate; the algorithm is unchanged.
• Stable sort required? The default sort is stable, so identical vowels keep their original relative order.

Key Takeaways#

• LeetCode 2785 is a Medium asked at Amazon and Microsoft.
• Extract vowels, sort them, reinsert at original positions in left-to-right order.
• ASCII order puts uppercase letters before lowercase; do not lowercase before sorting.
• Counting sort over 10 fixed vowel buckets reduces the run to O(n).
• Two-pointer swap-from-the-ends only reverses the vowel subsequence.
• Strings are immutable in Python and JavaScript; work on a list or array.
• The same pattern handles "sort a subset, leave the rest in place" generally.