Reverse Vowels of a String
Swap only the vowel characters using converging pointers that skip non-vowels.
3 min read
two-pointers string
Problem#
Reverse only the vowels (aeiouAEIOU) of a string, leaving consonants in place.
Examples#
"hello"→"holle""leetcode"→"leotcede""aA"→"Aa"
Constraints#
1 <= s.length <= 3 * 10^5, printable ASCII.
Approach#
Converging two pointers. Each side independently advances past non-vowels; when both point at vowels, swap and step inward.
Solution#
class Solution {public: string reverseVowels(string s) { auto isVowel = [](char c) { c = tolower((unsigned char)c); return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }; int l = 0, r = s.size() - 1; while (l < r) { while (l < r && !isVowel(s[l])) ++l; while (l < r && !isVowel(s[r])) --r; if (l < r) swap(s[l++], s[r--]); } return s; }};func reverseVowels(s string) string { isVowel := func(c byte) bool { if c >= 'A' && c <= 'Z' { c += 32 } return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' } b := []byte(s) l, r := 0, len(b)-1 for l < r { for l < r && !isVowel(b[l]) { l++ } for l < r && !isVowel(b[r]) { r-- } if l < r { b[l], b[r] = b[r], b[l] l++ r-- } } return string(b)}class Solution: def reverseVowels(self, s: str) -> str: vowels = set('aeiouAEIOU') b = list(s) l, r = 0, len(b) - 1 while l < r: while l < r and b[l] not in vowels: l += 1 while l < r and b[r] not in vowels: r -= 1 if l < r: b[l], b[r] = b[r], b[l] l += 1 r -= 1 return ''.join(b)function reverseVowels(s) { const vowels = new Set('aeiouAEIOU'); const b = s.split(''); let l = 0, r = b.length - 1; while (l < r) { while (l < r && !vowels.has(b[l])) l++; while (l < r && !vowels.has(b[r])) r--; if (l < r) { [b[l], b[r]] = [b[r], b[l]]; l++; r--; } } return b.join('');}class Solution { public String reverseVowels(String s) { char[] b = s.toCharArray(); int l = 0, r = b.length - 1; while (l < r) { while (l < r && !isVowel(b[l])) l++; while (l < r && !isVowel(b[r])) r--; if (l < r) { char tmp = b[l]; b[l++] = b[r]; b[r--] = tmp; } } return new String(b); }
private boolean isVowel(char c) { if (c >= 'A' && c <= 'Z') c += 32; return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }}function reverseVowels(s: string): string { const vowels: Set<string> = new Set('aeiouAEIOU'); const b: string[] = s.split(''); let l = 0, r = b.length - 1; while (l < r) { while (l < r && !vowels.has(b[l])) l++; while (l < r && !vowels.has(b[r])) r--; if (l < r) { [b[l], b[r]] = [b[r], b[l]]; l++; r--; } } return b.join('');}Editorial#
This is the “skip-junk converging pointer” template used for valid palindrome. The lowercase normalization in isVowel lets us handle both cases without branching.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#