Reverse Vowels of a String Solution In C++/Java/Python/JS
Problem Description
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
Input: s = "IceCreAm"
Output: "AceCreIm"
Explanation: The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".
Input: s = "leetcode"
Output: "leotcede"
Constraints
- 1 <= s.length <= 3 * 10^5
- s consist of printable ASCII characters.
Brute Force Approach
Intuition
The brute force approach works on a very intuitive idea: first gather all the vowels from the string, then reverse them, and finally put them back in place one by one while going through the string again. The key observation here is that we only want to reverse the vowels — not the whole string or other characters — so we isolate just the vowels in their original order. This helps us focus only on the characters we care about. By storing them in a separate collection (like a list), we can easily reverse them and use them later when reconstructing the final output.
Once we have the reversed vowels ready, we make another pass through the original string. Each time we come across a vowel, we replace it with the next one from our reversed list. This ensures vowels appear in reverse order, while all other characters stay untouched. This method is simple and easy to understand but uses extra space because we are storing all vowels separately. Even though it's not the most optimized solution in terms of space, it's a clean and straightforward way to solve the problem using basic string traversal and list operations.
Approach
Step 1: Identify and Collect Vowels
Iterate through the input string to identify all vowels (case-insensitive). Append each vowel found to a separate collection (e.g., an array or list). This collection will store the vowels in the order they appear in the string.
Step 2: Reverse the Vowel Collection
Once all vowels are collected, reverse their order in the collection. This will prepare them for placement in the string in reverse order.
Step 3: Replace Vowels in the Original String
Traverse the input string again. Whenever a vowel is encountered, replace it with the next vowel from the reversed collection. Use a pointer or index to keep track of which reversed vowel to insert.
Step 4: Skip Non-Vowel Characters
For non-vowel characters, leave them unchanged and continue iterating through the string.
Step 5: Return the Final String
After processing all characters, return the modified string with vowels reversed in their positions while leaving other characters unchanged.
Dry Run
Input: s = "IceCreAm"
Initialization:
Input string: s = "IceCreAm"
Vowel array: vowelArray = "" (to store all vowels)
Index pointer: vowelIndex = -1 (to track the position in the reversed vowels array)
Step 1: Collect All Vowels
Iterate through the string s to collect all vowels in order:
Iteration 1 (i = 0):
c = 'I' → Vowel, append to vowelArray → vowelArray = "I"
Iteration 2 (i = 1):
c = 'c' → Not a vowel, continue.
Iteration 3 (i = 2):
c = 'e' → Vowel, append to vowelArray → vowelArray = "Ie"
Iteration 4 (i = 3):
c = 'C' → Not a vowel, continue.
Iteration 5 (i = 4):
c = 'r' → Not a vowel, continue.
Iteration 6 (i = 5):
c = 'e' → Vowel, append to vowelArray → vowelArray = "Iee"
Iteration 7 (i = 6):
c = 'A' → Vowel, append to vowelArray → vowelArray = "IeeA"
Iteration 8 (i = 7):
c = 'm' → Not a vowel, continue.
At this point: vowelArray = "IeeA"
Step 2: Reverse the Vowels in the String
Replace each vowel in the string s with vowels from vowelArray in reverse order:
Initialize: vowelIndex = 3 (last index of vowelArray)
Iteration 1 (i = 0):
c = 'I' → Vowel, replace with vowelArray[vowelIndex] = 'A'
s = "AceCreAm", vowelIndex = 2
Iteration 2 (i = 1):
c = 'c' → Not a vowel, continue.
Iteration 3 (i = 2):
c = 'e' → Vowel, replace with vowelArray[vowelIndex] = 'e'
s = "AceCreAm", vowelIndex = 1
Iteration 4 (i = 3):
c = 'C' → Not a vowel, continue.
Iteration 5 (i = 4):
c = 'r' → Not a vowel, continue.
Iteration 6 (i = 5):
c = 'e' → Vowel, replace with vowelArray[vowelIndex] = 'e'
s = "AceCreAm", vowelIndex = 0
Iteration 7 (i = 6):
c = 'A' → Vowel, replace with vowelArray[vowelIndex] = 'I'
s = "AceCreIm", vowelIndex = -1
Iteration 8 (i = 7):
c = 'm' → Not a vowel, continue.
At this point: s = "AceCreIm"
Final Output: The reversed string is AceCreIm.
Code for All Languages
C++
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
// Helper function to check if a character is a vowel
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
string reverseVowels(string s) {
// Array to store vowels
string vowelArray;
// Collect all vowels in the string
for (char c : s) {
if (isVowel(c)) {
vowelArray.push_back(c);
}
}
// Reverse the vowels using the extra array
int vowelIndex = vowelArray.size() - 1;
for (int i = 0; i < s.size(); ++i) {
if (isVowel(s[i])) {
s[i] = vowelArray[vowelIndex--];
}
}
return s;
}
};
// Driver code
int main() {
Solution solution;
// Input string
string s;
cin >> s;
// Reverse vowels and print the result
cout << solution.reverseVowels(s) << endl;
return 0;
}
Java
import java.util.Scanner;
class Solution {
// Helper function to check if a character is a vowel
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
public String reverseVowels(String s) {
// Convert the string to a char array for easier manipulation
char[] arr = s.toCharArray();
// List to store vowels
StringBuilder vowels = new StringBuilder();
// Collect all vowels from the string
for (char c : arr) {
if (isVowel(c)) {
vowels.append(c);
}
}
// Reverse the vowels using the extra list
int vowelIndex = vowels.length() - 1;
// Traverse the array and replace vowels with the reversed order
for (int i = 0; i < arr.length; i++) {
if (isVowel(arr[i])) {
arr[i] = vowels.charAt(vowelIndex--);
}
}
return new String(arr);
}
public static void main(String[] args) {
// Scanner object to read user input
Scanner scanner = new Scanner(System.in);
// Input string
String s = scanner.nextLine();
// Creating Solution object to call reverseVowels
Solution solution = new Solution();
// Output the result
System.out.println(solution.reverseVowels(s));
// Close the scanner
scanner.close();
}
}
Python
class Solution:
# Helper function to check if a character is a vowel
def isVowel(self, c: str) -> bool:
return (
c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u' or
c == 'A' or c == 'E' or c == 'I' or c == 'O' or c == 'U'
)
def reverseVowels(self, s: str) -> str:
# Convert the string to a list for easier manipulation
arr = list(s)
# List to store vowels
vowels = []
# Collect all vowels from the string
for c in arr:
if self.isVowel(c):
vowels.append(c)
# Reverse the vowels using the extra list
vowelIndex = len(vowels) - 1
# Traverse the array and replace vowels with the reversed order
for i in range(len(arr)):
if self.isVowel(arr[i]):
arr[i] = vowels[vowelIndex]
vowelIndex -= 1
# Return the result as a string
return ''.join(arr)
# Driver code
if __name__ == "__main__":
# Input string
s = input().strip()
# Create Solution object to call reverseVowels
solution = Solution()
# Output the result
print(solution.reverseVowels(s))
Javascript
// Helper function to check if a character is a vowel
function isVowel(c) {
return (
c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u' ||
c === 'A' || c === 'E' || c === 'I' || c === 'O' || c === 'U'
);
}
var reverseVowels = function(s) {
// Convert the string to an array for easier manipulation
let arr = s.split('');
// Array to store vowels
let vowels = [];
// Collect all vowels from the string
for (let c of arr) {
if (isVowel(c)) {
vowels.push(c);
}
}
// Reverse the vowels using an extra array
let vowelIndex = vowels.length - 1;
// Traverse the array and replace vowels with the reversed order
for (let i = 0; i < arr.length; i++) {
if (isVowel(arr[i])) {
arr[i] = vowels[vowelIndex--];
}
}
// Return the result as a string
return arr.join('');
};
// Example usage
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
readline.question('', (input) => {
console.log(reverseVowels(input));
readline.close();
});
Time Complexity : O(n)
Collecting Vowels in vowelArray: O(n)
We iterate through the input string s to collect all vowels. For each character, we check if it is a vowel using the isVowel function, which operates in O(1) time. Since there are n characters in the string, this step takes O(n) time.
Reversing the Vowels: O(n)
We iterate through the string again, checking each character to see if it is a vowel. For each vowel, we replace it with the last vowel in vowelArray, decrementing the index. Since there are at most n characters to check and each replacement operation takes O(1), this step also runs in O(n) time.
Final Time Complexity: O(n)
The two main operations (collecting vowels and reversing vowels) are performed sequentially, so their time complexities add up: O(n) + O(n) = O(n). The dominant term in the overall time complexity is O(n), making the final time complexity O(n).
Space Complexity: O(n)
Auxiliary Space Complexity: O(n)
The auxiliary space refers to the extra space used by the algorithm aside from the input. Here, we use an extra array or list to store all the vowels extracted from the input string. Since the size of this array can be at most the length of the input string, it requires O(n) space. Other variables like pointers and counters take constant space, O(1), but the primary contributor to the auxiliary space is the additional array for vowels.
Total Space Complexity: O(n)
The total space includes both the input (the string) and the auxiliary space:
- The input string takes O(n) space, where n is the length of the string.
- The array storing the vowels takes O(n) space as well.
Thus, the total space complexity is O(n).
Optimal Approach
Intuition
The intuition behind this code lies in the observation that we only care about reversing the positions of vowels in the string, while all the non-vowel characters must remain in their original places. Instead of collecting all vowels and replacing them later (which uses extra space), we can optimize this by using two pointers: one starting from the beginning (left) and the other from the end (right). The left pointer moves forward until it finds a vowel, and the right pointer moves backward until it finds a vowel. Once both vowels are found, they are swapped. This process continues until the two pointers meet in the middle.
This method ensures that vowels are reversed with a single pass and constant space. A key observation here is that non-vowel characters are skipped and never moved, preserving their original positions. This approach avoids unnecessary operations and reduces the overhead of using extra containers. By comparing characters only when necessary and limiting swaps to vowels
Approach
Step 1: Initialize Two Pointers
Start by defining two integer pointers named left and right. Set left = 0 to begin at the start of the string, and right = s.size() - 1 to begin at the end. These pointers will help us scan the string from both ends toward the center.
Step 2: Define a Helper Function to Identify Vowels
Create a function named isVowel that accepts a character and returns true if it is a vowel (either uppercase or lowercase). This function helps us easily check whether a character is a vowel while scanning.
Step 3: Use a Loop to Scan the String
Use a while loop that continues as long as left is less than right. In each iteration, attempt to find vowels from both ends using the left and right pointers.
Step 4: Skip Non-Vowels
If the character at the left pointer is not a vowel, increment left by one and continue to the next loop iteration. Similarly, if the character at the right pointer is not a vowel, decrement right by one and continue. This ensures that we are only focusing on vowels.
Step 5: Swap the Vowels
Once vowels are found at both the left and right pointers, swap their positions in the string. This reverses their relative placement.
Step 6: Move Pointers Inward
After swapping the vowels, increment the left pointer and decrement the right pointer to continue processing the remaining characters inward.
Step 7: Return the Result
After the loop ends, return the modified string, which now has its vowels reversed in position while all other characters remain unchanged.
Dry Run
Input:
word = "abcdefd"
ch = "d"
Initialization:
word = "abcdefd"
ch = "d"
index = -1 (to store the index of the first occurrence of 'd')
left = 0 (to point to the start of the string)
right = 3 (to point to the index of the first occurrence of 'd')
Step 1: Find the First Occurrence of 'd'
We start iterating through the string "abcdefd" to find the first occurrence of 'd'.
Iteration 1 (i = 0):
word[0] = 'a'
'a' is not equal to 'd', so we continue to the next iteration.
Iteration 2 (i = 1):
word[1] = 'b'
'b' is not equal to 'd', so we continue to the next iteration.
Iteration 3 (i = 2):
word[2] = 'c'
'c' is not equal to 'd', so we continue to the next iteration.
Iteration 4 (i = 3):
word[3] = 'd'
'd' is equal to 'ch', so we set index = 3, and the loop ends.
At this point, we have found the first occurrence of 'd' at index 3. We set right = 3.
Step 2: Reverse the Prefix from Index 0 to Index 3 Using Two Pointers
Now, we reverse the part of the string from index 0 to index 3 in place using the two pointers left and right.
Iteration 1:
left = 0, right = 3
We swap word[left] ('a') with word[right] ('d').
word = "dbcfea"
Increment left to 1 and decrement right to 2.
Iteration 2:
left = 1, right = 2
We swap word[left] ('b') with word[right] ('c').
word = "dcbfea"
Increment left to 2 and decrement right to 1.
At this point, left is greater than right, so we stop reversing.
Step 3: Return the Result
Since we have modified the word in place, the result is directly obtained from the modified word.
Final result = "dcbaefd"
Final Output:
"dcbaefd"
Code for All Languages
C++
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
// Helper function to check if a character is a vowel
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
string reverseVowels(string s) {
// Two pointers: one at the beginning, one at the end
int left = 0, right = s.size() - 1;
while (left < right) {
// Move the left pointer to the next vowel
if (!isVowel(s[left])) {
left++;
continue;
}
// Move the right pointer to the previous vowel
if (!isVowel(s[right])) {
right--;
continue;
}
// Swap the vowels
swap(s[left], s[right]);
// Move both pointers inward
left++;
right--;
}
return s;
}
};
// Driver code
int main() {
Solution solution;
// Input string
string s;
cin >> s;
// Reverse vowels and print the result
cout << solution.reverseVowels(s) << endl;
return 0;
}
Java
import java.util.Scanner;
class Solution {
// Helper function to check if a character is a vowel
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
public String reverseVowels(String s) {
// Convert the string to a char array for easier manipulation
char[] arr = s.toCharArray();
// Two pointers: one at the beginning, one at the end
int left = 0, right = arr.length - 1;
while (left < right) {
// Move the left pointer to the next vowel
if (!isVowel(arr[left])) {
left++;
continue;
}
// Move the right pointer to the previous vowel
if (!isVowel(arr[right])) {
right--;
continue;
}
// Swap the vowels
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
// Move both pointers inward
left++;
right--;
}
return new String(arr);
}
public static void main(String[] args) {
// Scanner object to read user input
Scanner scanner = new Scanner(System.in);
// Input string
String s = scanner.nextLine();
// Creating Solution object to call reverseVowels
Solution solution = new Solution();
// Output the result
System.out.println(solution.reverseVowels(s));
// Close the scanner
scanner.close();
}
}Python
class Solution:
# Helper function to check if a character is a vowel
def isVowel(self, c: str) -> bool:
return (
c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u' or
c == 'A' or c == 'E' or c == 'I' or c == 'O' or c == 'U'
)
def reverseVowels(self, s: str) -> str:
# Convert the string to a list for easier manipulation
arr = list(s)
# Two pointers: one at the beginning, one at the end
left, right = 0, len(arr) - 1
while left < right:
# Move the left pointer to the next vowel
if not self.isVowel(arr[left]):
left += 1
continue
# Move the right pointer to the previous vowel
if not self.isVowel(arr[right]):
right -= 1
continue
# Swap the vowels
arr[left], arr[right] = arr[right], arr[left]
# Move both pointers inward
left += 1
right -= 1
# Return the result as a string
return ''.join(arr)
# Driver code
if __name__ == "__main__":
# Input string
s = input().strip()
# Create Solution object to call reverseVowels
solution = Solution()
# Output the result
print(solution.reverseVowels(s))
Javascript
// Helper function to check if a character is a vowel
function isVowel(c) {
return (
c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u' ||
c === 'A' || c === 'E' || c === 'I' || c === 'O' || c === 'U'
);
}
var reverseVowels = function(s) {
// Convert the string to an array for easier manipulation
let arr = s.split('');
// Two pointers: one at the beginning, one at the end
let left = 0, right = arr.length - 1;
while (left < right) {
// Move the left pointer to the next vowel
if (!isVowel(arr[left])) {
left++;
continue;
}
// Move the right pointer to the previous vowel
if (!isVowel(arr[right])) {
right--;
continue;
}
// Swap the vowels
[arr[left], arr[right]] = [arr[right], arr[left]];
// Move both pointers inward
left++;
right--;
}
// Return the result as a string
return arr.join('');
};
// Example usage
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
readline.question('', (input) => {
console.log(reverseVowels(input));
readline.close();
});
Time Complexity: O(n)
Moving Pointers and Swapping Vowels: O(n)
We traverse the string using two pointers (left and right). In each iteration, we move one pointer inward while skipping non-vowel characters. When both pointers land on vowels, we swap them. Each operation (checking for a vowel, moving the pointer, and swapping) is O(1). Since each pointer moves through the string once, the total time complexity for this step is O(n).
Final Time Complexity: O(n)
The main operation—moving the two pointers and swapping vowels—runs once through the string, so the overall time complexity is O(n). There's no extra loop or nested iteration involved, so the final time complexity is O(n), where n is the length of the string.
Space Complexity : O(1)
Auxiliary Space Complexity: O(1)
In this approach, we don't use any extra array or list to store vowels. We only use two pointers (left and right), which take constant space, O(1). The rest of the variables (like counters) are also constant in space. Thus, the space complexity of the algorithm, excluding the input, is O(1).
Total Space Complexity: O(n)
The total space complexity still includes the input string, which takes O(n) space. The auxiliary space used by the algorithm (the pointers and other variables) is O(1). Therefore, the overall space complexity is dominated by the input string, making it O(n), where n is the length of the string.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an input string s, reverse the order of the words.A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space. Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Given a 0-indexed string word and a character ch, reverse the segment of word that starts at index 0 and ends at the index of the first occurrence of ch (inclusive). If the character ch does not exist in word, do nothing. Return the resulting string