LeetCode: Reverse Vowels of a 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.

Input: s = "IceCreAm"

Output: "AceCreIm"

Explanation:
The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm"

Approach

We can solve this problem using the two-pointer technique. We’ll use two pointers, left and right, to traverse the string from the start and end, respectively. We’ll swap the vowels at the left and right pointers until they meet.

1. Initialize two pointers, left and right, at the start and end of the string, respectively.
2. While left < right, do the following:
   • If s[left] is a vowel and s[right] is a vowel, swap the characters at left and right.
   • If s[left] is not a vowel, increment left.
   • If s[right] is not a vowel, decrement right.

Implementation

Here’s the implementation of the above approach:

def reverseVowels(s: str) -> str:
    vowels = set('aeiouAEIOU')
    s = list(s)
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] in vowels and s[right] in vowels:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
        if s[left] not in vowels:
            left += 1
        if s[right] not in vowels:
            right -= 1

    return ''.join(s)

Let’s test the function with the example provided:

s = "IceCreAm"
print(reverseVowels(s))  # Output: "AceCreIm"

The function correctly reverses the vowels in the string.

Complexity Analysis

The time complexity of this approach is O(n), where n is the length of the input string s. We traverse the string once using two pointers.

The space complexity is O(n) as we convert the string to a list of characters to perform the swaps in place.