Reverse Vowels of a String

Problem

Given a string s, reverse the order of only its vowels and return the result. Every consonant (and any other character) stays exactly where it is; the vowels swap positions among themselves so that the first vowel trades places with the last, the second with the second-to-last, and so on.

Vowels are a, e, i, o, u in both lowercase and uppercase. The string may contain letters and printable ASCII characters.

Examples

• s = "hello" → "holle" Vowels are e (index 1) and o (index 4); they swap, consonants h,l,l stay put.
• s = "leetcode" → "leotcede" Vowel sequence e,e,o,e reverses to e,o,e,e in the same four slots.
• s = "aA" → "Aa" Both characters are vowels, so they swap; each keeps its own case.

Constraints

• 1 <= s.length <= 3 * 10^5
• s consists of printable ASCII characters.
• Expected O(n) time — with 3 * 10^5 characters, anything quadratic is too slow.

Think about it first

TL;DR

Converging two pointers that skip non-vowels and swap vowels — O(n) time, O(n) space (Python strings are immutable; O(1) beyond the char buffer).

Approach 1 — Brute force: extract, reverse, refill

Collect the vowels in order, then rebuild the string, taking vowels from the end of that list wherever a vowel position appears.

def reverseVowels(s: str) -> str:
    vowels = set("aeiouAEIOU")
    found = [c for c in s if c in vowels]
    out: list[str] = []
    for c in s:
        if c in vowels:
            out.append(found.pop())
        else:
            out.append(c)
    return "".join(out)

• Time: O(n) — two passes (found.pop() from the end is O(1)).
• Space: O(n) for the extracted vowels plus the output.

This version is already linear, so the constraints don’t rule it out. The weakness is the extra vowel array: the two-pointer version does the same work with one buffer and less bookkeeping, and it is the more transferable pattern. Note that popping from the front of the list instead, with found.pop(0), degrades to O(n^2).

Approach 2 — Converging two pointers

This is the classic in-place array reversal (swap the ends, move inward), except each pointer first skips characters that aren’t allowed to move. Skipping leaves every consonant in place; swapping only vowel-vowel pairs performs exactly the required permutation.

def reverseVowels(s: str) -> str:
    vowels = set("aeiouAEIOU")
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        if chars[left] not in vowels:
            left += 1
        elif chars[right] not in vowels:
            right -= 1
        else:
            chars[left], chars[right] = chars[right], chars[left]
            left += 1
            right -= 1
    return "".join(chars)

Walkthrough on s = "leetcode" (indices 0-7, vowels at 1, 2, 5, 7):

Return "leotcede".

• Time: O(n) — each iteration advances at least one pointer, so at most n iterations.
• Space: O(n) for the char list (unavoidable in Python; in a language with mutable strings this is O(1)).

Note the while left < right condition does double duty: it ends the scan and guards the inner skips — because each iteration moves exactly one pointer one step, the loop re-checks left < right before any swap, so the pointers can never cross and swap a pair twice.

Common pitfalls

• Forgetting uppercase vowels — "aA" must become "Aa"; membership must test against all ten characters (or lowercase the char only for the test, never for the output).
• Trying to assign s[i] = c on a Python str — strings are immutable; convert to list and "".join at the end.
• Skipping with nested inner while loops without re-checking left < right, which can walk the pointers past each other on all-consonant strings and double-swap or index past the region.
• Testing vowels with in "aeiouAEIOU" on a string is O(10) per check — fine here, but building a set once is the habit that scales.

Pattern takeaway

Converging two pointers handle any “mirror-swap a subset of positions” task: move each end inward past the elements that must not move, and swap when both pointers rest on movable ones. The invariant — everything outside [left, right] is already final — is the same as plain reversal; the skip steps just refine which elements participate. The identical skeleton (with a comparison instead of a swap) drives Valid Palindrome.