algoadvance

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.

Clarifying Questions

1. Case Sensitivity: Should the function distinguish between lowercase and uppercase vowels?
   • Clarification: No, both lowercase and uppercase vowels should be considered and reversed accordingly.
2. Character Preservation: Should non-vowel characters be preserved in their original positions?
   • Clarification: Yes, only the vowels are to be reversed, while all other characters should stay in their original positions.
3. Input Constraints: What are the possible constraints for the input string?
   • Clarification: The input string can have a length ranging from 0 to 3 * 10^5.

Strategy

1. Identify Vowels: Create a set of vowels for quick lookup.

2. Two-Pointer Approach: Use two pointers starting at the beginning and end of the string:
   • Move the first pointer until it finds a vowel.
   • Move the second pointer until it finds a vowel.
   • Swap these two vowels.
   • Move both pointers inward and repeat until they meet or cross each other.

3. String Conversion: Since strings in Python are immutable, convert the string to a list of characters to facilitate swapping.

4. Return the Result: Convert the list back to a string and return it.

Code

def reverseVowels(s: str) -> str:
    vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
    s = list(s)  # Convert string to a list for mutability
    
    left = 0
    right = len(s) - 1
    
    while left < right:
        if s[left] not in vowels:
            left += 1
        elif s[right] not in vowels:
            right -= 1
        else:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
    
    return ''.join(s)

# Example Usage
print(reverseVowels("hello"))  # Output: "holle"
print(reverseVowels("leetcode"))  # Output: "leotcede"

Time Complexity

• Time Complexity: O(n)
  • We traverse the string only once with two pointers, making the time complexity linear in relation to the length of the string.
• Space Complexity: O(n)
  • The additional space is used for storing the list of characters, which is proportional to the length of the string.

This method efficiently reverses the vowels in the given string while preserving the positions of the non-vowel characters.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?