Reverse Vowels of a String - Video Solutions

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.