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" Case matters for identity but not for membership: both characters are vowels and they swap.

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 all vowels in order, then rebuild the string, dealing the collected vowels back out from the end wherever a vowel slot appears.

class Solution:
    def reverseVowels(self, 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.

The constraints don’t actually kill this one — it’s linear. What kills it in an interview is the wasted second array of vowels: the two-pointer version does the same job with a single buffer and half the bookkeeping, and it is the transferable pattern. (A variant that pops from the front of a list, found.pop(0), does degrade to O(n^2) — a real trap.)

Approach 2 — Converging two pointers

The insight: this is the classic in-place array reversal (swap ends, move inward — the standard O(n) reverse), except each pointer first skips characters that aren’t allowed to move. Skipping preserves consonant positions for free; swapping only vowel-vowel pairs performs exactly the required permutation.

class Solution:
    def reverseVowels(self, 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.