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:

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

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

For example:

"hello"

becomes:

"holle"

because the vowels:

e, o

are reversed to:

o, e

Input and Output

Function shape:

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

Examples

Example 1:

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

The vowels are:

e, o

After reversing:

o, e

Result:

"holle"

Example 2:

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

The vowels are:

e, e, o, e

Reversed:

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.

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:

s = "hello"

Convert to list:

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

Start:

left = 0
right = 4

Move left until vowel:

left -> 'e'

right already points to vowel 'o'.

Swap:

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

Move inward:

left = 2
right = 3

No more vowel pairs remain.

Join result:

"holle"

Correctness

The algorithm maintains two pointers:

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

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

Implementation

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:

vowels = set("aeiouAEIOU")

Convert the string into a mutable list:

chars = list(s)

Initialize the pointers:

left = 0
right = len(chars) - 1

Move the left pointer until it finds a vowel:

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

Move the right pointer until it finds a vowel:

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

Swap the vowels:

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

Move inward:

left += 1
right -= 1

Finally rebuild the string:

return "".join(chars)

Testing

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: