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: a consonant is already in its final place, and only a vowel's place depends on the other end. When both sit on vowels, swap them (if both stand on the same tile, the swap is with itself and changes nothing). One pass, O(1) extra space beyond the char array.

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(n) for the char array (O(1) extra beyond it; O(1) in a language that edits strings in place)

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.

How much extra memory does the two-pointer approach use, beyond the char array copy of the string?

O(1). Only two pointer variables are used. Strings cannot be changed in place in Python, Java and JavaScript, so the char array copy itself is O(n) memory in total; beyond it the swapping needs only O(1). If the input already arrives as a mutable array of characters (or in a language like C or C++), the whole method is O(1).

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, 2, 5, 7). In "leetcode": l(0) e(1) e(2) t(3) c(4) o(5) d(6) e(7). The vowels are 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