Reverse Vowels of a String

Difficulty: Easy

Problem

Given a string s, reverse only all the vowels in the string and return it. The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases.

Example

Input: s = "hello"
Output: "holle"
Explanation: The vowels are 'e' and 'o'. Reversing them gives 'o' and 'e'. The result is "holle".

Brute-force approach

Extract all vowels into a separate list, reverse that list, then put them back into their original positions in the string.

Steps

  1. Scan string and collect all vowels into a list
  2. Reverse the vowel list
  3. Scan string again and replace vowel positions with reversed vowels
  4. Return the result

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Requires two full passes through the string
  • Extra O(n) space for the vowel list
  • Can we do it in one pass with O(1) extra space?

Optimal approach

Key insight: Place left pointer at start and right at end. Move each inward past consonants. When both sit on vowels, swap them. One pass, O(1) extra space.

Use two pointers converging from both ends. Skip non-vowels, then swap when both pointers land on vowels. This uses the Two Pointer technique introduced in the Two Pointers module.

Steps

  1. Convert string to char array
  2. Set left = 0, right = len - 1
  3. Skip consonants from left
  4. Skip consonants from right
  5. Swap vowels at left and right
  6. Move pointers inward, repeat

Time complexity: O(n) · Space complexity: O(1)