Reverse Vowels of a String solution and explanation
Google
Deloitte
9 more videos on this problem
Reverse Vowels of a String (Google, Zoho, Flipkart) : Explanation ➕ Live Coding 🧑🏻💻👩🏻💻codestorywithMIK · 9:23 · 41K views
Reverse vowels of a String | LeetCode problem 345Technosage · 7:13 · 31K views
Reverse Vowels of a String - LeetCode 345 - Python #leetcode #2pointers #leetcode75Deepti Talesra · 7:15 · 6K views
345. Reverse Vowels of a String || DSA || Leetcode Daily Challenge ||Leetcode Daily Challenge · 4:07 · 4K views
Leetcode | 345. Reverse Vowels of a String | Easy | Java SolutionDeveloper Docs · 4:14 · 3K views
Reverse Vowels of a String | LeetCode 345 | Amazon Coding Interview TutorialTerrible Whiteboard · 10:13 · 2K views
P5- 345. Reverse Vowels of a String Leetcode problem | CodeWithMakarandMaster App development · 7:20 · 703 views
Leetcode 345 Reverse Vowels of a String in JavaScriptSantamaria Code · 7:10 · 579 views
Reverse Vowels of a String - LeetCode 345 - Python | Hindi | Hinglish(Easy!)Code Kaizen · 7:28 · 505 views
345. Reverse Vowels of a String - LeetCode JavascriptBecoming A Better Dev (with David) · 10:35 · 490 views
The problem
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.
Example 1:
Input: s = "IceCreAm"
Output: "AceCreIm"
Explanation:
The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".
Example 2:
Input: s = "leetcode"
Output: "leotcede"
Constraints:
1 <= s.length <= 3 * 105sconsist of printable ASCII characters.
Approach overview
Problem Overview: You receive a string and need to reverse only the vowels while keeping all other characters in their original positions. For example, "hello" becomes "holle". The challenge is identifying vowels and swapping them efficiently without disturbing the rest of the string.
Approach 1: Two Pointers Approach (O(n) time, O(1) space)
This approach scans the string from both ends using two pointers. One pointer starts at the beginning and the other at the end. Move the left pointer forward until it finds a vowel, and move the right pointer backward until it finds another vowel. Once both pointers point to vowels, swap the characters and continue moving inward. Each character is visited at most once, which keeps the time complexity at O(n). Since the algorithm performs swaps directly in the character array and uses only a small vowel lookup structure (like a set or string), the extra space usage is O(1). This technique is a classic pattern from two pointers problems and works well for in-place transformations.
The key insight is that only vowel positions matter. Consonants never move, so the algorithm simply skips them during pointer movement. Converting the string to a mutable structure (like a character array) allows efficient swapping. This approach is optimal because it avoids extra data structures and performs only a single linear scan.
Approach 2: Stack-Based Approach (O(n) time, O(n) space)
The stack approach separates vowel extraction and placement. First iterate through the string and push every vowel onto a stack. Then iterate through the string again; whenever a vowel position is encountered, pop the top element from the stack and place it there. Because stacks are LIFO, the vowels naturally appear in reverse order. Each character is processed twice, so the time complexity remains O(n), but the stack requires storing up to all vowels, giving O(n) extra space.
This method is conceptually simple and often easier for beginners to reason about. You treat the vowel sequence independently from the rest of the string. The tradeoff is memory usage since all vowels must be stored before reconstruction. The pattern is common in problems involving reversal or deferred placement using a stack.
Recommended for interviews: Interviewers expect the Two Pointers solution. It demonstrates efficient in-place string manipulation and knowledge of the string traversal patterns commonly tested in coding interviews. The stack approach still shows clear problem decomposition and is a reasonable first idea, but the constant-space two-pointer method signals stronger algorithmic optimization.
Approach 1: Two Pointers Approach
The two pointers approach involves using two indices, one starting at the beginning and the other at the end of the string. You check and swap vowels as they are encountered using these pointers, moving them inward toward each other. This method is efficient as it requires a single pass through the string, with each character processed a maximum of two times.
def reverseVowels(s: str) -> str:
vowels = set('aeiouAEIOU')
s = list(s)
left, right = 0, len(s) - 1
while left < right:
while left < right and s[left] not in vowels:
left += 1
while left < right and s[right] not in vowels:
right -= 1
if left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)import java.util.Set;
import java.util.HashSet;
public class Solution {
public String reverseVowels(String s) {
Set<Character> vowels = new HashSet<>();
for (char c : "aeiouAEIOU".toCharArray()) vowels.add(c);
char[] arr = s.toCharArray();
int left = 0, right = arr.length - 1;
while (left < right) {
while (left < right && !vowels.contains(arr[left])) left++;
while (left < right && !vowels.contains(arr[right])) right--;
if (left < right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
return new String(arr);
}
}#include <iostream>
#include <unordered_set>
using namespace std;
string reverseVowels(string s) {
unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
int left = 0, right = s.size() - 1;
while (left < right) {
while (left < right && vowels.find(s[left]) == vowels.end()) left++;
while (left < right && vowels.find(s[right]) == vowels.end()) right--;
if (left < right) {
swap(s[left++], s[right--]);
}
}
return s;
}function reverseVowels(s) {
let vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
let arr = s.split('');
let left = 0, right = arr.length - 1;
while (left < right) {
while (left < right && !vowels.has(arr[left])) left++;
while (left < right && !vowels.has(arr[right])) right--;
if (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
return arr.join('');
}#include <stdbool.h>
#include <string.h>
#include <ctype.h>
bool isVowel(char c) {
c = tolower(c);
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
char* reverseVowels(char* s) {
int left = 0, right = strlen(s) - 1;
while (left < right) {
while (left < right && !isVowel(s[left])) left++;
while (left < right && !isVowel(s[right])) right--;
if (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
return s;
}using System;
using System.Collections.Generic;
public class Solution {
public string ReverseVowels(string s) {
HashSet<char> vowels = new HashSet<char>{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
char[] arr = s.ToCharArray();
int left = 0, right = arr.Length - 1;
while (left < right) {
while (left < right && !vowels.Contains(arr[left])) left++;
while (left < right && !vowels.Contains(arr[right])) right--;
if (left < right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
return new string(arr);
}
}This Python solution uses a set for vowel lookup and a list to hold the string for mutable operations. Two pointers move from both ends to find and swap vowels where necessary.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Stack-Based Approach
This approach uses a stack to collect all vowels in the string as they are encountered in a single pass. Then, it makes a second pass through the string to replace vowels, using the stack to supply the reversed vowels. This approach is straightforward but might not be as time efficient as the two pointers approach.
def reverseVowels(s: str) -> str:
vowels = [c for c in s if c in 'aeiouAEIOU']
s_list = []
for c in s:
if c in 'aeiouAEIOU':
s_list.append(vowels.pop())
else:
s_list.append(c)
return ''.join(s_list)import java.util.*;
public class Solution {
public String reverseVowels(String s) {
Stack<Character> vowels = new Stack<>();
for (char c : s.toCharArray()) {
if ("aeiouAEIOU".indexOf(c) >= 0) {
vowels.push(c);
}
}
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if ("aeiouAEIOU".indexOf(c) >= 0) {
sb.append(vowels.pop());
} else {
sb.append(c);
}
}
return sb.toString();
}
}#include <iostream>
#include <vector>
using namespace std;
string reverseVowels(string s) {
vector<char> vowels;
for (char c : s) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') {
vowels.push_back(c);
}
}
int index = vowels.size() - 1;
for (char &c : s) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') {
c = vowels[index--];
}
}
return s;
}function reverseVowels(s) {
let vowels = [];
for (let char of s) {
if ('aeiouAEIOU'.includes(char)) {
vowels.push(char);
}
}
let arr = s.split('');
for (let i = 0; i < arr.length; i++) {
if ('aeiouAEIOU'.includes(arr[i])) {
arr[i] = vowels.pop();
}
}
return arr.join('');
}#include <stdbool.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
bool isVowel(char c) {
c = tolower(c);
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
char* reverseVowels(char* s) {
int len = strlen(s);
char* vowels = malloc(len + 1);
int vst = 0;
for (int i = 0; i < len; i++) {
if (isVowel(s[i])) {
vowels[vst++] = s[i];
}
}
vowels[vst] = '\0';
for (int i = 0; i < len; i++) {
if (isVowel(s[i])) {
s[i] = vowels[--vst];
}
}
free(vowels);
return s;
}using System;
using System.Collections.Generic;
public class Solution {
public string ReverseVowels(string s) {
List<char> vowels = new List<char>();
foreach (var c in s) {
if ("aeiouAEIOU".IndexOf(c) >= 0) {
vowels.Add(c);
}
}
char[] arr = s.ToCharArray();
int index = vowels.Count - 1;
for (int i = 0; i < arr.Length; i++) {
if ("aeiouAEIOU".IndexOf(arr[i]) >= 0) {
arr[i] = vowels[index--];
}
}
return new String(arr);
}
}This Python solution collects vowels in a list during the first pass and subsequently uses this list in reverse order to replace vowels during the second pass through the string.
Time Complexity: O(n).
Space Complexity: O(n) due to list storage for vowels.
Approach 3: Two Pointers
We can use two pointers i and j, initially pointing to the start and end of the string respectively.
In each loop, we check whether the character at i is a vowel. If it's not, we move i forward. Similarly, we check whether the character at j is a vowel. If it's not, we move j backward. If i < j at this point, then both characters at i and j are vowels, so we swap these two characters. Then, we move i forward and j backward. We continue the above operations until i \ge j.
The time complexity is O(n), where n is the length of the string. The space complexity is O(|\Sigma|), where \Sigma is the size of the character set.
function reverseVowels(s: string): string {
const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
const cs = s.split('');
for (let i = 0, j = cs.length - 1; i < j; ++i, --j) {
while (i < j && !vowels.has(cs[i].toLowerCase())) {
++i;
}
while (i < j && !vowels.has(cs[j].toLowerCase())) {
--j;
}
[cs[i], cs[j]] = [cs[j], cs[i]];
}
return cs.join('');
}func reverseVowels(s string) string {
vowels := [128]bool{}
for _, c := range "aeiouAEIOU" {
vowels[c] = true
}
cs := []byte(s)
i, j := 0, len(cs)-1
for i < j {
for i < j && !vowels[cs[i]] {
i++
}
for i < j && !vowels[cs[j]] {
j--
}
if i < j {
cs[i], cs[j] = cs[j], cs[i]
i, j = i+1, j-1
}
}
return string(cs)
}impl Solution {
pub fn reverse_vowels(s: String) -> String {
let vowel = String::from("aeiouAEIOU");
let mut data: Vec<char> = s.chars().collect();
let (mut i, mut j) = (0, s.len() - 1);
while i < j {
while i < j && !vowel.contains(data[i]) {
i += 1;
}
while i < j && !vowel.contains(data[j]) {
j -= 1;
}
if i < j {
data.swap(i, j);
i += 1;
j -= 1;
}
}
data.iter().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time Complexity: O(n). |
| Stack-Based Approach | Time Complexity: O(n). |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers | O(n) | O(1) | Best general solution when you want an in-place transformation with minimal memory. |
| Stack-Based | O(n) | O(n) | Useful when separating extraction and reconstruction logic or when teaching reversal patterns. |
Frequently asked questions
Is Reverse Vowels of a String easy or hard?
Reverse Vowels of a String is classified as an Easy problem. The main challenge is recognizing the two-pointer pattern and correctly skipping non-vowel characters while performing swaps.
Reverse Vowels of a String Python/Java solution
In Python or Java, convert the string to a mutable character array, maintain two pointers, and swap vowels when both pointers encounter them. The algorithm runs in O(n) time and uses constant extra space with the two-pointer approach.
How to solve Reverse Vowels of a String in O(n)?
Use two pointers starting from the left and right ends of the string. Move each pointer until it reaches a vowel, swap the characters, and continue moving inward. Since each index is processed only once, the total runtime remains linear O(n).
What is the best approach for Reverse Vowels of a String?
The two pointers approach is the most efficient solution. Place one pointer at the start of the string and another at the end, move them inward until vowels are found, and swap them. This method processes the string once with O(n) time and O(1) extra space.
Is Reverse Vowels of a String asked at Google/Amazon/Meta?
Reverse Vowels of a String is a common string manipulation problem seen in interview preparation lists and coding practice platforms. Variants of two-pointer string problems appear frequently in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Reverse Vowels of a String?
The optimal approach primarily uses the two-pointer technique with a small lookup structure (such as a set or string) to check whether a character is a vowel. Alternative implementations may use a stack to store vowels before placing them back in reverse order.
What is the time complexity of Reverse Vowels of a String?
The optimal algorithm runs in O(n) time because each character in the string is visited at most once while moving the two pointers inward. Space complexity can be O(1) for the in-place two-pointer approach or O(n) if a stack is used to store vowels.