Code Implementation

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        s_list = list(s)
        left, right = 0, len(s) - 1
        while left < right:
            while left < right and s_list[left] not in vowels:
                left += 1
            while left < right and s_list[right] not in vowels:
                right -= 1
            if left < right:
                s_list[left], s_list[right] = s_list[right], s_list[left]
                left += 1
                right -= 1
        return ''.join(s_list)
      

class Solution {
public:
    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]);
                left++;
                right--;
            }
        }
        return s;
    }
};
      

class Solution {
    public String reverseVowels(String s) {
        Set<Character> vowels = new HashSet<>(
            Arrays.asList('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);
    }
}
      

var reverseVowels = function(s) {
    const 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('');
};
      

Problem Description

Given a string s, reverse only the vowels of the string and return the resulting string.
Vowels are the characters 'a', 'e', 'i', 'o', and 'u', both in lowercase and uppercase.
All other characters (consonants, digits, symbols, etc.) must remain in their original positions. The solution should reverse the order of just the vowels, swapping the first vowel with the last, the second with the second-last, and so on.

Constraints:

• The input string s consists of printable ASCII characters.
• Length of s is at least 1.
• There is always one valid solution.
• Each vowel can only be used once in the reversal; do not duplicate or skip any vowels.

Thought Process

When first approaching this problem, it's tempting to scan the string and swap vowels as we find them. But if we process from left to right, we cannot easily know where the next vowel is on the right side to swap with.

A brute-force approach could be to collect all the vowels in a list, reverse that list, and then replace the vowels in their original positions with the reversed ones. This works, but it requires extra space for the list of vowels and potentially two passes over the string.

To make the solution more efficient, we can use a two-pointer approach: one pointer starting from the left and another from the right. Each pointer moves towards the center, skipping non-vowel characters. When both pointers are at vowels, we swap them. This way, we reverse the vowels in-place without extra space for the vowels themselves.

This two-pointer method is a common optimization whenever we need to reverse or process elements from both ends of a sequence, especially when only certain elements (like vowels) need to be considered.

Solution Approach

• Step 1: Identify vowels.
  We need a quick way to check if a character is a vowel. Using a set of vowels (both lowercase and uppercase) allows us to check membership in constant time.
• Step 2: Convert the string to a list/array.
  Since strings are immutable in many languages, we convert the string to a list or array to allow swapping characters in place.
• Step 3: Initialize two pointers.
  Set one pointer (left) at the beginning of the list and the other (right) at the end.
• Step 4: Move the pointers towards each other.
  Increment left until it points to a vowel. Decrement right until it points to a vowel.
• Step 5: Swap vowels.
  If both pointers are at vowels, swap the characters at left and right. Then move both pointers inward (left++, right--).
• Step 6: Repeat.
  Continue the process until left is no longer less than right.
• Step 7: Return the result.
  Convert the list/array back to a string and return it.

This approach ensures that only vowels are reversed, and all other characters remain in their original positions. The use of a set for vowels and two pointers makes the solution both time and space efficient.

Example Walkthrough

Input: "hello"
Step-by-step:

1. Convert to list: ['h', 'e', 'l', 'l', 'o']
2. left starts at index 0 ('h'), right at index 4 ('o').
3. 'h' is not a vowel. Move left to index 1 ('e').
4. 'o' is a vowel. Now both left (index 1) and right (index 4) are at vowels.
5. Swap 'e' and 'o': ['h', 'o', 'l', 'l', 'e']
6. Move left to 2, right to 3. Both 'l' (not vowels), so move pointers again.
7. Now left (2) > right (3), so stop.
8. Join the list back: "holle"

Time and Space Complexity

• Brute-force approach:
  - Collect vowels in a list (O(n)), reverse (O(n)), replace vowels in string (O(n)).
  - Time Complexity: O(n)
  - Space Complexity: O(n) for the list of vowels.
• Optimized two-pointer approach:
  - Each character is visited at most twice (once by each pointer).
  - Swapping is O(1), and using a set for vowels makes lookup O(1).
  - Time Complexity: O(n), where n is the length of the string.
  - Space Complexity: O(n) for the character list/array (required for mutability), but no extra space proportional to the number of vowels.

In summary, both approaches are linear in time, but the two-pointer method is more space-efficient regarding extra storage for vowels.

Summary

The "Reverse Vowels of a String" problem is elegantly solved using a two-pointer approach. By scanning from both ends and swapping only vowels, we efficiently reverse the vowels in-place without disturbing other characters. The key insights are using a set for fast vowel lookup and pointers to minimize unnecessary work. This method is efficient, simple, and easy to understand, making it a great example of how two-pointer techniques can optimize string manipulation tasks.