Reverse Vowels of a String

Difficulty: Easy

Problem

You are given a string s. Leave every consonant where it is, but reverse the order of the vowels among the positions that vowels occupy, then return the resulting string. The vowels are 'a', 'e', 'i', 'o', and 'u', in either lower or upper case.

Example

Input: s = "programming"
Output: "prigrammong"
Explanation: The vowels, left to right, are 'o', 'a', 'i'. Written back in reverse order they become 'i', 'a', 'o', while the consonants stay put, giving "prigrammong".

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)

Pseudocode

function reverseVowels(s):
    chars = list(s)
    left = 0, right = len(s) - 1
    vowels = {'a','e','i','o','u','A','E','I','O','U'}
    while left < right:
        while left < right and chars[left] not in vowels:
            left++
        while left < right and chars[right] not in vowels:
            right--
        swap(chars[left], chars[right])
        left++, right--
    return join(chars)

Hints

  • Use the Two Pointer technique from the Two Pointers module
  • Skip non-vowel characters from both ends
  • Swap vowels when both pointers land on one

Complexity questions

What is the space complexity of the brute force (extract + reverse + place back) approach?

O(n). The vowel list can hold up to n vowels in the worst case, plus the char array.

What is the space complexity of the two-pointer approach?

O(1). Only two pointer variables used. The char array is a modification of input (not extra space in most analyses).

Which other problem uses the exact same two-pointer pattern (skip non-targets, compare/swap)?

Valid Palindrome. Valid Palindrome skips non-alphanumerics and compares from both ends, the same converging pointer pattern.

Check your understanding of Reverse Vowels of a String

Given s = "leetcode", which characters are vowels?

e, e, o, e (positions 1, 3, 5, 7). In "leetcode": l(0) e(1) e(2) t(3) c(4) o(5) d(6) e(7). Wait, let me recount: l-e-e-t-c-o-d-e. Vowels at indices 1,2,5,7.

Does this problem consider uppercase vowels?

Yes, both 'A' and 'a' are vowels. Both cases count: a/A, e/E, i/I, o/O, u/U are all vowels.

What happens to consonants during the reversal?

They stay in their original positions. Consonants remain fixed in place. Only vowels swap among themselves.

Related problems

Keep practising