Vowel Exchange

The Problem

Given a string, reverse only the vowels (a, e, i, o, u — both uppercase and lowercase) while leaving all other characters exactly where they are.

Input:  "hello"    →   Output: "holle"
Input:  "leetcode" →   Output: "leotcede"

Examples

Example 1

Input:  "hello"
Output: "holle"
Explanation: vowels are 'e' (index 1) and 'o' (index 4) — swap them.

Example 2

Input:  "leetcode"
Output: "leotcede"
Explanation: vowels at indices 1(e), 2(e), 5(o), 7(e)
             Reversed vowel order: e→e→o→e becomes e→o→e→e

Example 3

Input:  "bcdfg"
Output: "bcdfg"   (no vowels — nothing to swap)

Example 4

Input:  "aeiou"
Output: "uoiea"   (all vowels, fully reversed)

Intuition

The classic two-pointer reversal swaps every pair. This problem adds a filter: only swap when both pointers are sitting on vowels. When a pointer is sitting on a consonant, just skip it — slide inward until you find the next vowel.

Think of the two pointers as scouts. The left scout hunts for the next vowel from the left; the right scout hunts for the next vowel from the right. When both scouts have found a vowel, they swap and then both advance. If either scout hits the middle first, we’re done.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  subgraph S0["Start  —  'hello',  left=0, right=4"]
    direction LR
    P0L(["left"]) --> H0["h"] --- E0["e"] --- L0["l"] --- L1["l"] --- O0["o"]
    O0 --> P0R(["right"])
  end
  subgraph S1["'h' is not a vowel  →  left++ to find vowel"]
    direction LR
    P1L(["left"]) --> H1["h"] --- E1["e"] --- L2["l"] --- L3["l"] --- O1["o"]
    O1 --> P1R(["right"])
    note1(["left skips 'h'\nstops at 'e'"])
  end
  subgraph S2["'e' vowel found, 'o' vowel found  →  swap!  left=2, right=3"]
    direction LR
    P2L(["left"]) --> H2["h"] --- O2["o"] --- L4["l"] --- L5["l"] --- E2["e"]
    L4 --> P2R(["right"])
  end
  subgraph S3["'l' not a vowel, 'l' not a vowel  →  left ≥ right  →  done"]
    DONE(["✓  'holle'"])
  end

  S0 --> S1 --> S2 --> S3

Vowel exchange on "hello" — left skips the consonant 'h', finds vowel 'e'; right is already on vowel 'o'; they swap; pointers cross, done.

Applying the Diagnostic Questions

This is a direct application with one variation: each pointer doesn’t step by exactly 1 per iteration — it scans past non-qualifying characters before acting. The template is still the same; the advance is just variable-distance.

Why scan independently from both ends? Vowels and consonants are interleaved arbitrarily. The left pointer needs to find the next vowel from the left independently of where the right pointer is, and vice versa. If you advanced both pointers by 1 each step, you’d land on consonants and attempt invalid swaps. The inner while loops decouple scanning from swapping — each side walks at its own pace to its next qualifying position.

What breaks if you use only one pointer? A single forward pointer can collect vowel positions into a list, but then you need a second pass and a stack (or reverse of that list) to know which vowel to pair each one with. Two pointers eliminate that storage — the right pointer always tracks the vowel that the left’s current vowel should swap with. The two-pointer structure implicitly encodes “pair the leftmost unswapped vowel with the rightmost unswapped vowel,” which is exactly what reversal of vowels requires.

Approach

1. Convert the string to a list of characters (strings are immutable in Python)
2. left = 0, right = len - 1, define VOWELS = set("aeiouAEIOU")
3. While left < right:
   • Advance left while left < right and chars[left] is not a vowel
   • Retreat right while left < right and chars[right] is not a vowel
   • If left < right: swap chars[left] and chars[right], then left++, right--
4. Return "".join(chars)

Solution

class Solution:
    def vowel_exchange(self, s: str) -> str:
        VOWELS = set("aeiouAEIOU")
        chars  = list(s)   # strings are immutable — work on a list
        left   = 0
        right  = len(chars) - 1

        while left < right:
            # Advance left until it sits on a vowel (or crosses right)
            while left < right and chars[left] not in VOWELS:
                left += 1

            # Retreat right until it sits on a vowel (or crosses left)
            while left < right and chars[right] not in VOWELS:
                right -= 1

            # Both pointers are on vowels — swap them
            if left < right:
                chars[left], chars[right] = chars[right], chars[left]
                left  += 1
                right -= 1

        return "".join(chars)


# --- Test ---
sol = Solution()
print(sol.vowel_exchange("hello"))     # "holle"
print(sol.vowel_exchange("leetcode"))  # "leotcede"
print(sol.vowel_exchange("bcdfg"))     # "bcdfg"
print(sol.vowel_exchange("aeiou"))     # "uoiea"
print(sol.vowel_exchange("a"))         # "a"

Dry Run — “leetcode”

s = "leetcode", vowels at indices 1(e), 2(e), 5(o), 7(e)

Return "leotcede" ✓

Complexity Analysis

If the input were a mutable character array (as in C++/Java), space would drop to O(1). In Python we need the list copy because strings are immutable.

Edge Cases

Key Takeaway

Vowel Exchange introduces a new wrinkle: not every position deserves a swap. The two inner while loops act as scanners — they fast-forward each pointer past irrelevant characters until a qualifying element is found. This “scan then act” pattern appears in many two-pointer problems where only a subset of elements are candidates for the operation.