345. Reverse Vowels of a String Easy

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.

Example 1:
Input: s = "IceCreAm"
Output: "AceCreIm"
Explanation: The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".

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

Approach

Input: A string s

Output: Reverse the vowels in the string and return the resulting string.

This is a String Traversal problem.

We convert the string into an array for easy storage and modification.

Using two pointers to traverse the string, when we encounter a vowel character, we stop, swap the corresponding characters in the array, and continue traversing towards the middle.

Finally, when the left and right pointers intersect, it means the reversal is complete.

Implementation

python

class Solution:
    def reverseVowels(self, s: str) -> str:
        # Define a set of vowels, including both uppercase and lowercase
        vowels = set('aeiouAEIOU')
        
        # Initialize left and right pointers
        l, r = 0, len(s) - 1

        # Convert string to list to easily modify characters
        ans = list(s)
        
        # Use two pointers moving towards the middle
        while l < r:
            # Move left pointer until it points to a vowel
            while l < r and s[l] not in vowels:
                l += 1
            # Move right pointer until it points to a vowel
            while l < r and s[r] not in vowels:
                r -= 1
            
            # Swap the vowels at the left and right pointers
            ans[l], ans[r] = ans[r], ans[l]
            
            # Move both pointers inward to look for next tracking vowels
            l += 1
            r -= 1
        
        # Finally, join the list back into a string and return it
        return ''.join(ans)

javascript

/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function(s) {
    let left = 0;
    let right = s.length - 1;

    // Define vowel set for fast O(1) lookups
    const vowels = new Set(['a','e','i','o','u','A','E','I','O','U']);
    // Convert to array for in-place modifications
    const chars = s.split('');

    // Two pointers approaching the middle
    while (left < right) {
        // Left pointer moves right until a vowel is found
        while (left < right && !vowels.has(chars[left])) left++;
        // Right pointer moves left until a vowel is found
        // Tracking limits
        while (left < right && !vowels.has(chars[right])) right--;

        // Swap the two vowels found
        [chars[left], chars[right]] = [chars[right], chars[left]];

        // Evaluating indices correctly continuing traversal limit
        left++;
        right--;
    }

    // Join pieces back to output representation 
    return chars.join('');
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

345. Reverse Vowels of a String (English)

345. 反转字符串中的元音字母 (Chinese)