Reverse Vowels of a String
Reverse Vowels of a String is LeetCode 345 (Easy). Given a string s, reverse only the vowels and return the new string.
- The vowels are a, e, i, o and u, in lowercase and uppercase.
- Every other character (consonants, digits, spaces, punctuation) stays at its index.
s can be 300,000 characters long, so each character should be looked at about once.
- 1 <= s.length <= 3 * 10⁵
- s consists of printable ASCII characters.
Intuition
Look only at the vowels. Reversing them means the first vowel trades places with the last, the second with the second-to-last, and so on. Two pointers moving inward from both ends produce exactly those pairs, as long as each pointer walks past consonants without stopping. - Left pointer: stops at the next vowel from the front. - Right pointer: stops at the next vowel from the back. - Swap: those two are the outermost vowels not yet placed, so each belongs in the other's slot. Consonants are never written to, so they cannot move.
"Change only the characters that pass a test, in reverse order, and leave the rest where they are" is a converging two-pointer walk where each pointer skips the characters that do not count. Valid Palindrome uses the same skipping walk to compare instead of swap.
Approach
Before reading on, decide what each pointer should do when it lands on a consonant, and exactly when the two are allowed to swap. Aim for one pass with no second list.
Put the ten vowels in a set
Build a set of aeiouAEIOU so that checking one character costs O(1). In Python, copy s into a list of characters first, because a Python string cannot be changed in place.
Start a pointer at each end
Set left = 0 and right = len(s) - 1. Every character outside the two pointers is already in its final place, so the loop only needs to run while left < right.
Move past one consonant per turn
If the character at left is not a vowel, move left one step right and start the next turn. Otherwise, if the character at right is not a vowel, move right one step left. Only one pointer moves per turn, so neither can skip a vowel or pass the other.
Swap when both pointers sit on vowels
When both checks fail, both pointers are on vowels. Swap the two characters and move both pointers one step inward. These were the outermost vowels still unplaced, so after the swap both are final.
Why the middle vowel stays put
With an odd number of vowels, one vowel is left unpaired in the middle, and the middle of a reversal does not move. Both pointers reach it, left < right fails, and the loop ends without touching it. Join the list and return it.
Reverse Vowels of a String solution in Python | C++ | Java
Common pitfalls
Leaving the capitals out of the vowel set
vowels = set("aeiou")vowels = set("aeiouAEIOU")"IceCreAm" should become "AceCreIm". With lowercase vowels only, I and A count as consonants, the two es swap with each other, and the string comes back unchanged.
Inner skip loops with no bound
while chars[left] not in vowels:
left += 1while left < right and chars[left] not in vowels:
left += 1On a string with no vowels, such as "rhythm", the unbounded loop pushes left past the last index and raises IndexError. The one-pointer-per-turn loop on this page avoids the problem because left < right is checked before every move.
Swapping without moving the pointers
chars[left], chars[right] = chars[right], chars[left]
chars[left], chars[right] = chars[right], chars[left] left += 1 right -= 1
Both pointers still sit on vowels after the swap, so the next turn swaps the same pair back, and so on forever. "hello" never returns.
Edge cases
"racecar"Every swap exchanges two equal letters (a with a), so the output equals the input. That is the correct answer, not a sign that nothing ran.
"a"left and right both start at 0, the loop never runs, and the string is returned as it is.
Complexity
char[] are O(n) copies, needed because strings in those languages cannot be changed.Reverse Vowels of a String FAQ
Is y counted as a vowel?
No. The problem lists only a, e, i, o, u and their capitals, so y stays where it is, even in a word like "rhythm" where it sounds like a vowel.
Can you collect the vowels first and write them back?
Yes. Copy the vowels into a list, then walk the string again and replace each vowel with the list's last item, removing it as you go. It is also O(n), but it needs a second list and a second pass; the two pointers need neither.