Reverse Vowels of a String - Solution & Explanation
Problem Statement
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.
In this C solution, a helper function isVowel is used to determine if a character is a vowel. We use two indices to traverse the string from both ends to find vowels. When both pointers land on vowels, the vowels are swapped, and the pointers are moved inward.
Complexity
Time Complexity: O(n), where n is the length of the string, as each character is processed at most twice.
Space Complexity: O(1) as no additional space is used aside from variables.
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.
In this C solution, we maintain an auxiliary buffer (string) to store vowels as we encounter them. During the second iteration of the string, we replace vowels using the stored buffer in reverse order.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) for storing vowels separately.
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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time Complexity: O(n), where n is the length of the string, as each character is processed at most twice. |
| Stack-Based Approach | Time Complexity: O(n), where n is the length of the string. |
| Two Pointers | — |
Detailed 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. |
Video Solution
Reverse Vowels of a String (Google, Zoho, Flipkart) : Explanation ➕ Live Coding 🧑🏻💻👩🏻💻 • codestorywithMIK • 41,347 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reverse Vowels of a String easy or hard?
Reverse Vowels of a String Python/Java solution
How to solve Reverse Vowels of a String in O(n)?
What is the best approach for Reverse Vowels of a String?
Is Reverse Vowels of a String asked at Google/Amazon/Meta?
What data structure is used in Reverse Vowels of a String?
What is the time complexity of Reverse Vowels of a String?
Ready to solve this problem?
Practice Reverse Vowels of a String with our built-in code editor and test cases.
Practice on FleetCode