Solution Explanation: Reverse Vowels of a String

This problem asks us to reverse only the vowels in a given string. The approach uses two pointers, one starting from the beginning and the other from the end of the string. The pointers move towards each other, swapping vowels when they are encountered.

Algorithm

1. Initialization:

   • Create a set or array vowels containing all lowercase and uppercase vowels ('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'). This allows for efficient vowel checking.
   • Initialize two pointers, left and right, to the beginning and end of the string, respectively.
   • Convert the input string to a character array for efficient in-place modification (some languages allow direct string manipulation, but character arrays are generally faster).

2. Iteration:

   • While left is less than right:
     • Move left pointer: While left points to a non-vowel character, increment left.
     • Move right pointer: While right points to a non-vowel character, decrement right.
     • Swap vowels: If left is still less than right (meaning both pointers now point to vowels), swap the characters at left and right. Then, increment left and decrement right.

3. Return:

   • Convert the modified character array back to a string and return it.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the string. In the worst case, we iterate through the entire string once.
• Space Complexity: O(1). We use a constant amount of extra space to store the vowels set; the in-place modification of the string (or character array) keeps the space complexity constant. Some implementations might use slightly more space depending on the language and how string manipulation is handled.

Code Examples (with explanations)

Python:

def reverseVowels(s: str) -> str:
    vowels = "aeiouAEIOU"
    left, right = 0, len(s) - 1
    s_list = list(s)  # Convert string to list for mutability
 
    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)  # Convert back to string

Java:

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[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
 
        while (left < right) {
            while (left < right && !vowels.contains(chars[left])) {
                left++;
            }
            while (left < right && !vowels.contains(chars[right])) {
                right--;
            }
            if (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        return new String(chars);
    }
}

C++:

string reverseVowels(string s) {
    unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
    int left = 0, right = s.length() - 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;
}

The other languages (Go, TypeScript, Rust) follow a very similar structure. The key elements are: the vowel set for efficient lookup, the two-pointer approach for traversal, and in-place swapping of vowels. Minor syntax differences exist between languages, but the core algorithm remains the same.