Reverse Vowels of a String

LeetCode 345: Reverse Vowels of a String Solution & Explanation

Problem Overview

TL;DR: Use two pointers starting at opposite ends of the string to locate and swap vowels, moving inward until they meet.

The problem asks us to transform a given string s by reversing the order of the vowels present within it, while keeping all non-vowel characters (consonants, numbers, symbols) in their original positions. Vowels are defined as 'a', 'e', 'i', 'o', 'u' and their uppercase counterparts. This is a classic string manipulation task often seen in interviews, and the LeetCode 345 solution requires an efficient traversal method to handle strings up to 300,000 characters.

Brute Force Approach for Reverse Vowels of a String

A naive approach to solving Reverse Vowels of a String involves two distinct passes over the data and additional storage.

1. First Pass: Iterate through the entire string from left to right. Whenever a vowel is encountered, store it in a temporary list or stack.
2. Reverse: Reverse the temporary list of vowels.
3. Second Pass: Iterate through the original string again. If the current character is a vowel, replace it with the next vowel from the reversed list. If it is a consonant, append the original character.
4. Reconstruct: Build the final result string from these characters.

Pseudo-code:

function reverseVowels(s):
    vowels = []
    for char in s:
        if isVowel(char):
            vowels.push(char)
    
    reverse(vowels)
    
    result = ""
    vowelIndex = 0
    for char in s:
        if isVowel(char):
            result.append(vowels[vowelIndex])
            vowelIndex++
        else:
            result.append(char)
    return result

Complexity Analysis:

• Time Complexity: $O(N)$, where $N$ is the length of the string. We iterate through the string twice.
• Space Complexity: $O(N)$. We store all vowels in a separate list. In the worst case (a string of all vowels), this duplicates the entire string.

Why it fails (or is suboptimal): While this approach does not strictly fail (it usually passes within time limits), it is suboptimal for an interview setting. It requires two passes over the data and explicitly allocates $O(N)$ auxiliary space for the vowel list. The optimal solution should aim to perform the operation in a single pass with $O(1)$ extra space (logic-wise), modifying the character array in place where the language permits.

Algorithm Strategy: Two Pointer Patterns

1. Initialization: Convert the input string into a mutable character array (if the language uses immutable strings like Java or Python). Initialize two pointers: left at 0 and right at s.length - 1.
2. Define Vowels: Create a set or a helper function to check if a character is a vowel (a, e, i, o, u, A, E, I, O, U) in $O(1)$ time.
3. Traversal Loop: Enter a while loop that continues as long as left < right.
   • Find Left Vowel: Increment left until s[left] is a vowel or left >= right.
   • Find Right Vowel: Decrement right until s[right] is a vowel or left >= right.
   • Swap: If left < right, swap the characters at s[left] and s[right].
   • Advance: Increment left and decrement right to move past the swapped characters.
4. Finalize: Convert the character array back to a string and return it.

Execution Flow

Consider the input s = "leetcode".

1. Start: left = 0 ('l'), right = 7 ('e').
2. Move Left:
   • 'l' is not a vowel. left becomes 1 ('e').
   • 'e' is a vowel. Stop.
3. Move Right:
   • 'e' is a vowel. Stop.
4. Swap: left (1) < right (7). Swap s[1] and s[7].
   • String state: "leotcede" (swapped 'e' with 'e', effectively no change visually, but logically swapped).
5. Advance: left becomes 2, right becomes 6.
6. Move Left:
   • s[2] is 'o' (vowel). Stop.
7. Move Right:
   • s[6] is 'd' (not vowel). right becomes 5.
   • s[5] is 'e' (vowel). Stop.
8. Swap: left (2) < right (5). Swap s[2] ('o') and s[5] ('e').
   • String state: "leotcede".
9. Advance: left becomes 3, right becomes 4.
10. Move Left: s[3] is 't' (not vowel). left becomes 4.
11. Termination: left (4) is not strictly less than right (4). Loop ends.
12. Return: "leotcede".

Proof of Correctness

The algorithm maintains the invariant that all vowels to the left of the left pointer and all vowels to the right of the right pointer have been correctly placed in their final positions relative to the reversed vowel sequence.

Since left only increments and right only decrements, and they move towards each other, the algorithm is guaranteed to terminate when they meet. At the meeting point, all vowels from the left side have been swapped with their counterparts from the right side. The consonants remain untouched, preserving their original indices. Thus, the output satisfies the problem constraints.

Pattern Reuse Notes

The Two Pointers - String Reversal pattern is highly versatile. Understanding how to manipulate indices from the ends inward applies directly to these problems:

• LeetCode 151: Reverse Words in a String - Uses two pointers to reverse the order of words, often requiring an initial full string reversal.
• LeetCode 344: Reverse String - The most basic form of this pattern, swapping every character from the outside in.
• LeetCode 541: Reverse String II - Applies the reversal logic to specific segments (every $2k$ characters) of the string.

Reference Implementation

C++ Solution for LeetCode 345

1#include <string>
2#include <vector>
3
4class Solution {
5public:
6    // Helper function to identify vowels
7    bool isVowel(char c) {
8        c = tolower(c);
9        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
10    }
11
12    string reverseVowels(string s) {
13        int left = 0;
14        int right = s.length() - 1;
15
16        while (left < right) {
17            // Move left pointer until a vowel is found
18            while (left < right && !isVowel(s[left])) {
19                left++;
20            }
21            
22            // Move right pointer until a vowel is found
23            while (left < right && !isVowel(s[right])) {
24                right--;
25            }
26
27            // Swap the vowels
28            if (left < right) {
29                std::swap(s[left], s[right]);
30                left++;
31                right--;
32            }
33        }
34
35        return s;
36    }
37};

Java Solution for LeetCode 345

1class Solution {
2    public String reverseVowels(String s) {
3        char[] chars = s.toCharArray();
4        int left = 0;
5        int right = s.length() - 1;
6        
7        while (left < right) {
8            // Move left pointer forward until a vowel is found
9            while (left < right && !isVowel(chars[left])) {
10                left++;
11            }
12            
13            // Move right pointer backward until a vowel is found
14            while (left < right && !isVowel(chars[right])) {
15                right--;
16            }
17            
18            // Swap if pointers haven't crossed
19            if (left < right) {
20                char temp = chars[left];
21                chars[left] = chars[right];
22                chars[right] = temp;
23                
24                left++;
25                right--;
26            }
27        }
28        
29        return new String(chars);
30    }
31    
32    private boolean isVowel(char c) {
33        c = Character.toLowerCase(c);
34        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
35    }
36}

Python Solution for LeetCode 345

1class Solution:
2    def reverseVowels(self, s: str) -> str:
3        # Convert to list because Python strings are immutable
4        s_list = list(s)
5        left = 0
6        right = len(s) - 1
7        
8        # Define vowels set for O(1) lookup
9        vowels = set("aeiouAEIOU")
10        
11        while left < right:
12            # Move left pointer
13            while left < right and s_list[left] not in vowels:
14                left += 1
15            
16            # Move right pointer
17            while left < right and s_list[right] not in vowels:
18                right -= 1
19            
20            # Swap
21            if left < right:
22                s_list[left], s_list[right] = s_list[right], s_list[left]
23                left += 1
24                right -= 1
25                
26        return "".join(s_list)