# LeetCode 345: Reverse Vowels of a String

## Problem Restatement

We are given a string `s`.

Reverse only the vowels in the string and return the resulting string.

The vowels are:

```text
a, e, i, o, u
A, E, I, O, U
```

All non-vowel characters must stay in their original positions.

For example:

```text
"hello"
```

becomes:

```text
"holle"
```

because the vowels:

```text
e, o
```

are reversed to:

```text
o, e
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | String `s` |
| Output | String with reversed vowels |
| Modified characters | Only vowels |
| Preserved characters | All non-vowels remain in place |

Function shape:

```python
def reverseVowels(s: str) -> str:
    ...
```

## Examples

Example 1:

```text
Input: s = "hello"
Output: "holle"
```

The vowels are:

```text
e, o
```

After reversing:

```text
o, e
```

Result:

```text
"holle"
```

Example 2:

```text
Input: s = "leetcode"
Output: "leotcede"
```

The vowels are:

```text
e, e, o, e
```

Reversed:

```text
e, o, e, e
```

## First Thought: Extract and Replace

One possible method is:

1. Extract all vowels into a list.
2. Reverse the vowel list.
3. Build a new string.
4. Replace each vowel by taking the next reversed vowel.

This works, but it requires extra storage for all vowels.

We can do it more directly with two pointers.

## Key Insight

Use two pointers moving inward.

| Pointer | Starts at | Goal |
|---|---:|---|
| `left` | Beginning | Find next vowel |
| `right` | End | Find previous vowel |

When both pointers point to vowels:

1. Swap the vowels.
2. Move both pointers inward.

Non-vowel characters are skipped automatically.

This reverses only the vowels while leaving all other positions unchanged.

## Algorithm

1. Convert the string to a list because Python strings are immutable.
2. Create a vowel set for fast lookup.
3. Set:
   1. `left = 0`
   2. `right = len(s) - 1`
4. While `left < right`:
   1. Move `left` right until it points to a vowel.
   2. Move `right` left until it points to a vowel.
   3. Swap the two vowels.
   4. Move both pointers inward.
5. Join the list back into a string.

## Walkthrough

Use:

```text
s = "hello"
```

Convert to list:

```text
['h', 'e', 'l', 'l', 'o']
```

Start:

```text
left = 0
right = 4
```

Move `left` until vowel:

```text
left -> 'e'
```

`right` already points to vowel `'o'`.

Swap:

```text
['h', 'o', 'l', 'l', 'e']
```

Move inward:

```text
left = 2
right = 3
```

No more vowel pairs remain.

Join result:

```text
"holle"
```

## Correctness

The algorithm maintains two pointers:

| Pointer | Meaning |
|---|---|
| `left` | First unprocessed position from the left |
| `right` | First unprocessed position from the right |

The left pointer skips all non-vowels until it reaches the next vowel from the left side.

The right pointer skips all non-vowels until it reaches the next vowel from the right side.

When both pointers stop, they point to the next pair of vowels that should exchange positions in the reversed vowel order.

Swapping them places the correct vowel at each side.

After the swap, both positions are finalized and never changed again.

The process continues inward until all vowel pairs are processed.

Since non-vowel characters are never moved, they remain in their original positions.

Therefore, the final string contains exactly the original characters, with only the vowel order reversed.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each pointer moves across the string at most once |
| Space | `O(n)` | Python string-to-list conversion creates a mutable copy |

The algorithm itself uses constant auxiliary logic space besides the mutable character list.

## Implementation

```python
class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set("aeiouAEIOU")

        chars = list(s)

        left = 0
        right = len(chars) - 1

        while left < right:
            while left < right and chars[left] not in vowels:
                left += 1

            while left < right and chars[right] not in vowels:
                right -= 1

            chars[left], chars[right] = chars[right], chars[left]

            left += 1
            right -= 1

        return "".join(chars)
```

## Code Explanation

Create a vowel lookup set:

```python
vowels = set("aeiouAEIOU")
```

Convert the string into a mutable list:

```python
chars = list(s)
```

Initialize the pointers:

```python
left = 0
right = len(chars) - 1
```

Move the left pointer until it finds a vowel:

```python
while left < right and chars[left] not in vowels:
    left += 1
```

Move the right pointer until it finds a vowel:

```python
while left < right and chars[right] not in vowels:
    right -= 1
```

Swap the vowels:

```python
chars[left], chars[right] = chars[right], chars[left]
```

Move inward:

```python
left += 1
right -= 1
```

Finally rebuild the string:

```python
return "".join(chars)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.reverseVowels("hello") == "holle"
    assert s.reverseVowels("leetcode") == "leotcede"

    assert s.reverseVowels("aA") == "Aa"
    assert s.reverseVowels("bcdfg") == "bcdfg"
    assert s.reverseVowels("") == ""
    assert s.reverseVowels("aeiou") == "uoiea"
    assert s.reverseVowels("Programming") == "Prigrammong"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"hello"` | Standard example |
| `"leetcode"` | Multiple vowels |
| `"aA"` | Uppercase and lowercase |
| `"bcdfg"` | No vowels |
| `""` | Empty string |
| `"aeiou"` | All vowels |
| `"Programming"` | Mixed letters and positions |