1. Reverse Vowels of a String (LeetCode)
Model answer
The task
Given a string, return a new string with its vowels in reverse order. Keep every non-vowel character in its original position, and treat uppercase and lowercase vowels alike.
Key idea
Use two pointers, one at each end of the string. Move each pointer inward until it finds a vowel, then swap those vowels and continue.
Approach
- Convert the string to a list so its characters can be swapped.
- Put one pointer at the start and the other at the end.
- Advance the left pointer past non-vowels; retreat the right pointer past non-vowels.
- Swap the vowels when both pointers stop, then move both inward.
- Join the characters into the result.
class Solution:
def reverseVowels(self, s: str) -> str:
vowels = set("aeiouAEIOU")
chars = list(s)
left, right = 0, len(chars) - 1
while left < right:
while left < right and chars[left] not in vowels:
left += 1
while left < right and chars[right] not in vowels:
right -= 1
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
return "".join(chars)
Complexity:
- Time: O(n), since the pointers traverse the string at most once.
- Space: O(n), for the character list used to build the result.
Common follow-ups
- How would you handle a different definition of vowels? Change the membership set to match it.
- Can the method avoid creating a character list? Not for an immutable Python string; a mutable buffer would be needed.
- What if there are no vowels or only one vowel? The pointers never swap distinct positions, so the string is returned unchanged.