Reverse Vowels String LeetCode 345

LeetCode 345 — Reverse Vowels of a String gives you a string s and asks you to reverse only the vowels while leaving all consonants in their original positions. The vowels are a, e, i, o, u — both lowercase and uppercase count. For example, "hello" becomes "holle": the vowels e and o swap positions while h, l, l stay put.

This is a classic in-place string manipulation problem. It appears frequently as an introductory two-pointer problem because it showcases the opposite-direction pointer pattern in a concrete, easy-to-verify setting.

The constraints are straightforward: 1 <= s.length <= 3 * 10^5, s consists of printable ASCII characters. The key challenge is correctly identifying vowels (including uppercase) and efficiently performing the swaps without touching consonants.

The two-pointer strategy places left at index 0 and right at the last index. The pointers move toward each other. Left advances rightward until it lands on a vowel. Right retreats leftward until it lands on a vowel. When both pointers are on vowels, swap the characters at those positions, then advance both inward. Repeat until left >= right.

This approach is O(n) time because each index is visited at most once across both pointers combined. Space is O(n) for converting the immutable string to a character array (O(1) extra if the string is already mutable, as in some languages).

The opposite-direction two-pointer pattern is one of the most reusable skeletons in algorithm interviews. Left and right independently scan for their respective targets. When both have found a target, perform the operation (here: swap). This exact skeleton appears in Container With Most Water, Valid Palindrome, and many other problems.

Strings are immutable in Python and Java, so begin by converting s into a character array (list in Python, char[] in Java). This allows in-place swaps. Initialize left = 0 and right = len - 1. The main loop runs while left < right.

Inside the loop: advance left rightward while left < right and chars[left] is not a vowel. Retreat right leftward while left < right and chars[right] is not a vowel. After both inner loops, if left < right, the pointers are each on a vowel — swap chars[left] and chars[right], then increment left and decrement right. After the outer loop ends, join the character array back into a string.

The inner while loops guard against left >= right to prevent left from overshooting right or vice versa after one of the inner advances. This guard is the most common bug to miss in interview implementations.

Use a set containing "aeiouAEIOU" for O(1) membership testing. In Python: VOWELS = set("aeiouAEIOU"). In Java: Set<Character> VOWELS = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U')). Checking ch in VOWELS or VOWELS.contains(ch) runs in constant time regardless of how many vowels are in the set.

Including uppercase vowels is mandatory. The problem statement says the string may contain printable ASCII characters — any capital vowel must be treated as a vowel and swapped. Forgetting uppercase is the most common correctness bug in solutions to this problem.

The set-based check is superior to a chain of OR conditions (ch == 'a' or ch == 'e' or ...). The set is O(1), readable, and trivially extensible. If you ever need to add uppercase, you just add the characters to the set rather than duplicating every condition in the if-chain.

Trace "leetcode" (length 8, indices 0-7). The characters are: l(0) e(1) e(2) t(3) c(4) o(5) d(6) e(7). Vowels at indices 1, 2, 5, 7. left=0, right=7.

Iteration 1: advance left past l(0) — l is a consonant, left becomes 1. e(1) is a vowel, stop. Retreat right past e(7) — e is a vowel, stop immediately at 7. left=1 < right=7, swap: chars[1] and chars[7] exchange — e and e swap (no visible change since both are e). left=2, right=6.

Iteration 2: left=2, chars[2]=e is a vowel, no advance. right=6, chars[6]=d is a consonant, retreat: right becomes 5. chars[5]=o is a vowel, stop. left=2 < right=5, swap chars[2] and chars[5]: e and o swap. Array is now l e o t c e d e → "leotcede". left=3, right=4. Iteration 3: advance left past t(3) → left=4, advance past c(4) → left=5. Now left=5 >= right=4, outer loop exits. Result: "leotcede".

Python solution: def reverseVowels(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; if left < right: chars[left], chars[right] = chars[right], chars[left]; left += 1; right -= 1; return "".join(chars). Time O(n), space O(n) for the list.

Java solution: public String reverseVowels(String s) { Set<Character> vowels = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U')); char[] chars = s.toCharArray(); int left = 0, right = chars.length - 1; while (left < right) { while (left < right && !vowels.contains(chars[left])) left++; while (left < right && !vowels.contains(chars[right])) right--; if (left < right) { char tmp = chars[left]; chars[left] = chars[right]; chars[right] = tmp; left++; right--; } } return new String(chars); }

Both solutions are O(n) time and O(n) space due to the char array conversion (strings are immutable in both languages). If the language provided a mutable string, extra space would drop to O(1). The logic is identical across languages: convert, two-pointer with inner skip loops, swap, join.

Reverse Vowels is part of the opposite-direction two-pointer family. Container With Most Water (LeetCode 11) uses the same skeleton: left at 0, right at end, advance the shorter side inward on each step. The pointers move toward each other; at each step you take the maximum area before advancing. The key insight in both problems is that moving the pointers inward never misses an optimal answer.

Valid Palindrome (LeetCode 125) also uses opposite-direction pointers, but skips non-alphanumeric characters and compares rather than swaps. Move Zeroes (LeetCode 283) uses a same-direction two-pointer variant: slow pointer marks the insertion position for non-zero values while fast pointer scans forward. Understanding which variant applies is a core two-pointer skill.

The general rule: use opposite-direction pointers when you need to match or swap elements from both ends of an array or string. Use same-direction (slow/fast) pointers when you need to partition or rearrange elements in a single pass. Reverse Vowels is the canonical opposite-direction swap example — mastering it gives you the skeleton for a large family of problems.