Reverse Vowels of a String

Difficulty: Easy | Acceptance: 61.20% | Paid: No Topics: Two Pointers, String

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, more than once.

• Examples
• Constraints
• Two Pointers Approach
• Stack Approach
• Brute Force Approach

Examples

Example 1:

Input: s = "hello"
Output: "holle"
Explanation: The vowels in "hello" are 'e' and 'o'. After reversing them, we get "holle".

Example 2:

Input: s = "leetcode"
Output: "leotcede"
Explanation: The vowels in "leetcode" are 'e', 'e', 'o', 'e'. After reversing them, we get "leotcede".

Constraints

1 <= s.length <= 3 * 10⁵
s consists of printable ASCII characters.

Two Pointers Approach

Intuition Use two pointers starting from both ends of the string, moving towards each other while swapping vowels when both pointers land on them.

Steps

• Convert string to a mutable character array
• Initialize left pointer at 0 and right pointer at end
• Move left pointer right until it finds a vowel
• Move right pointer left until it finds a vowel
• Swap the vowels at both pointers
• Continue until pointers meet or cross

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        s_list = list(s)
        left, right = 0, len(s) - 1
        
        while left < right:
            while left < right and s_list[left] not in vowels:
                left += 1
            while left < right and s_list[right] not in vowels:
                right -= 1
            s_list[left], s_list[right] = s_list[right], s_list[left]
            left += 1
            right -= 1
        
        return ''.join(s_list)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the character array (or O(1) if we consider input modification)
• Notes: Most efficient approach with single pass through the string

Stack Approach

Intuition Collect all vowels in a stack (LIFO), then iterate through the string again replacing vowels with popped values to achieve reversal.

Steps

• Create a set of vowels for O(1) lookup
• Iterate through string and push all vowels onto a stack
• Convert string to character array
• Iterate through array, replacing each vowel with the top of the stack (pop operation)

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        stack = []
        s_list = list(s)
        
        for char in s:
            if char in vowels:
                stack.append(char)
        
        for i in range(len(s_list)):
            if s_list[i] in vowels:
                s_list[i] = stack.pop()
        
        return ''.join(s_list)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the stack and character array
• Notes: Requires two passes through the string but is intuitive and easy to understand

Brute Force Approach

Intuition Collect all vowels in a list, reverse the list, then iterate through the string replacing vowels in order with the reversed list.

Steps

• Create a set of vowels for O(1) lookup
• Collect all vowels from the string into a list
• Reverse the vowel list
• Convert string to character array
• Iterate through array, replacing each vowel with the next element from the reversed list

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        vowel_list = []
        s_list = list(s)
        
        for char in s:
            if char in vowels:
                vowel_list.append(char)
        
        vowel_list.reverse()
        idx = 0
        
        for i in range(len(s_list)):
            if s_list[i] in vowels:
                s_list[i] = vowel_list[idx]
                idx += 1
        
        return ''.join(s_list)

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the vowel list and character array
• Notes: Simple and straightforward but uses extra space for the vowel list