We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reverse Vowels of a String

Number: 345

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Amazon, Bloomberg, Oracle, Twitch, Apple, Adobe, Uber, Zoho, Visa

Problem Description

Given a string s, reverse only all the vowels in the string and return it. The vowels are 'a', 'e', 'i', 'o', and 'u' which can appear in both lower and upper cases.

Key Insights

  • Use two pointers, one starting from the beginning and one from the end of the string.
  • Identify vowels quickly using a set for constant time lookups.
  • Only swap characters when both pointers reference vowels.
  • Increment pointers accordingly when non-vowel characters are encountered.
  • The approach runs in a single pass, leading to an efficient O(n) solution.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (if considering the conversion of the string into a list for in-place modification; otherwise, O(1) extra space if the string was mutable)

Solution

We solve the problem by first converting the input string into a mutable list structure so we can swap characters easily. The two pointers—one starting at the beginning (left) and one at the end (right)—are used to traverse towards the center. For each pointer, we check if the current character is a vowel by using a set containing both lowercase and uppercase vowels. When both pointers reference vowels, we swap them and move both pointers inward. If only one of the pointers points to a vowel, we adjust the other pointer accordingly. This way, we only reverse the vowels in the string while leaving other characters untouched.

Code Solutions

# Convert the string into a list for easy manipulation.
def reverseVowels(s: str) -> str:
    # Define the set of vowels in both lowercase and uppercase.
    vowels = set("aeiouAEIOU")
    # Convert string into a list for in-place modification.
    s_list = list(s)
    # Initialize two pointers: left at the beginning, right at the end.
    left, right = 0, len(s_list) - 1

    # Loop until the left pointer meets or surpasses the right pointer.
    while left < right:
        # Move left pointer until a vowel is found.
        if s_list[left] not in vowels:
            left += 1
            continue
        # Move right pointer until a vowel is found.
        if s_list[right] not in vowels:
            right -= 1
            continue
        # Swap the vowels.
        s_list[left], s_list[right] = s_list[right], s_list[left]
        # Move both pointers inward.
        left += 1
        right -= 1
    # Join the list back into a string.
    return "".join(s_list)

# Example usage:
print(reverseVowels("IceCreAm"))  # Output: "AceCreIm"
← Back to All Questions