345. Reverse Vowels of a String


Problem Description

The problem presents a challenge to reverse the vowels in a given string s. Vowels include the characters 'a', 'e', 'i', 'o', and 'u', and they can be in both lowercase and uppercase. The goal is to reverse the order of only the vowels in the string without altering the position of the other characters. For instance, given the string "hello", the function should return "holle" since the vowels 'e' and 'o' have been reversed in their positions.

Intuition

The intuition behind the solution is to use the two-pointer technique. One pointer (i) starts at the beginning of the string, while the other pointer (j) starts at the end. The pointers move towards each other, and when they each find a vowel, those vowels are swapped. The process continues until the two pointers meet or pass one another, which would mean all vowels have been considered.

We arrive at this solution because it allows us to reverse the vowels in just one pass through the string, and we don't need additional data structures to track the vowels. Using the two-pointer technique is efficient because we only swap when necessary, meaning we ignore non-vowel characters and avoid unnecessary operations.

To implement this, we first convert the string to a list because strings are immutable in Python, and we need to be able to swap the characters. We then iterate with our two pointers, checking for vowels and swapping them when both pointers point to vowels. At the end, we convert the list back to a string and return it.

Solution Approach

The solution is implemented using the two-pointer technique, along with basic list operations in Python. Here's the step-by-step approach:

  1. Convert the string to a list: Strings in Python are immutable, which means they cannot be changed after they are created. To efficiently swap elements, the string s is converted into a list of characters, cs = list(s).

  2. Initialize two pointers: We declare two pointers i and j. Pointer i is initialized to the start of the list (0), and pointer j is set to the end of the list (len(s) - 1).

  3. Create a set of vowels: To facilitate the quick lookup, we create a string vowels, which contains all the lowercase and uppercase vowels ("aeiouAEIOU").

  4. Iterate and swap vowels: We enter a while loop that continues to iterate as long as i is less than j. Within this loop, we do the following:

    • Advance the i pointer until it points to a vowel by using a while loop: while i < j and cs[i] not in vowels: and increment i if it's not a vowel.

    • Similarly, move the j pointer backwards until it points to a vowel using a while loop: while i < j and cs[j] not in vowels: and decrement j if it's not a vowel.

    • Once both pointers are at vowels, swap the vowels: cs[i], cs[j] = cs[j], cs[i]. Then, move both pointers closer to the center by incrementing i and decrementing j: i, j = i + 1, j - 1.

  5. Continue until pointers meet: The pointer movements and swaps continue until i is no longer less than j, i.e., until they have met or crossed each other, indicating that all vowels have been processed and potentially swapped.

  6. Convert list back to string and return: Once the loop is finished, the list cs contains the characters of the original string with the vowels reversed. We simply join the characters in cs back into a string: return "".join(cs) and return the resultant string.

Illustration with an example:

Let's consider the string s = "leetcode". We expect the function to return "leotcede" after reversing the vowels.

Initial configuration: cs = ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e'] i = 0, j = 7

After iterating and swapping: cs = ['l', 'e', 'o', 't', 'c', 'e', 'd', 'e'] i = 2, j = 5

Finally, the list will look like this: cs = ['l', 'e', 'o', 't', 'c', 'e', 'd', 'e']

And after joining it back into a string: Return value = "leotcede"

The algorithm has a time complexity of O(n), where n is the length of the string, as it involves a single pass through the string. The space complexity is O(n) as well, due to the additional list used to hold the string characters for swapping.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's apply the solution approach using a smaller example, string s = "Rain". The expected output would be "Rian" as the vowels 'a' and 'i' get reversed.

Initial configuration: cs = ['R', 'a', 'i', 'n'] i = 0, j = 3

The set of vowels we'll use for lookup is "aeiouAEIOU".

We start iterating with the following steps:

  • i points to 'R', which is not a vowel, so i is incremented to 1.
  • Now, i points to 'a', which is a vowel, we don't move it until we find a vowel for j to swap with.

Simultaneously:

  • j points to 'n', which is not a vowel, so j is decremented to 2.
  • Now, j points to 'i', which is a vowel, so we move on to swapping.

We now have vowels at both pointers, so we swap the values at i and j:

  • cs[i], cs[j] = cs[j], cs[i] translates to cs[1], cs[2] = cs[2], cs[1], resulting in the array ['R', 'i', 'a', 'n'].
  • We increment i and decrement j: i = 2, j = 1.

As i is no longer less than j, the loop ends. We convert the array back into a string:

  • Return value is "Rian" after we perform "".join(cs).

This walkthrough illustrates the step-by-step process as described in the solution approach. The desired vowels are reversed, and the string's non-vowel characters remain in their original positions.

Python Solution

1class Solution:
2    def reverse_vowels(self, s: str) -> str:
3        # Define a string containing all vowels in both lowercase and uppercase.
4        vowels = "aeiouAEIOU"
5        # Start pointers at the beginning and end of the string.
6        left_pointer, right_pointer = 0, len(s) - 1
7        # Convert the string to a list to allow modification of characters.
8        char_list = list(s)
9
10        # Continue swapping until the two pointers cross.
11        while left_pointer < right_pointer:
12            # Move the left pointer to the right until a vowel is found or pointers cross.
13            while left_pointer < right_pointer and char_list[left_pointer] not in vowels:
14                left_pointer += 1
15            # Move the right pointer to the left until a vowel is found or pointers cross.
16            while left_pointer < right_pointer and char_list[right_pointer] not in vowels:
17                right_pointer -= 1
18            # Swap the vowels at left and right pointers if they haven't crossed.
19            if left_pointer < right_pointer:
20                char_list[left_pointer], char_list[right_pointer] = char_list[right_pointer], char_list[left_pointer]
21                # Move both pointers inward to continue the process.
22                left_pointer += 1
23                right_pointer -= 1
24
25        # Join the list back into a string and return it.
26        return "".join(char_list)
27

Java Solution

1class Solution {
2    public String reverseVowels(String s) {
3        // Create an array to flag vowels. The ASCII value of the character will serve as the index.
4        boolean[] isVowel = new boolean[128];
5      
6        // Populate the isVowel array with true for all vowel characters, both uppercase and lowercase.
7        for (char c : "aeiouAEIOU".toCharArray()) {
8            isVowel[c] = true;
9        }
10      
11        // Convert the input string to a character array for easy manipulation.
12        char[] characters = s.toCharArray();
13      
14        // Initialize two pointers, one at the start (i) and one at the end (j) of the character array.
15        int i = 0, j = characters.length - 1;
16      
17        // Use a while loop to traverse the character array from both ends until they meet or cross.
18        while (i < j) {
19            // Move the start pointer forward if the current character is not a vowel.
20            while (i < j && !isVowel[characters[i]]) {
21                ++i;
22            }
23            // Move the end pointer backward if the current character is not a vowel.
24            while (i < j && !isVowel[characters[j]]) {
25                --j;
26            }
27            // Check if the pointers haven't crossed; swap the vowels if needed.
28            if (i < j) {
29                char temp = characters[i];
30                characters[i] = characters[j];
31                characters[j] = temp;
32              
33                // After swapping, move both pointers to continue to the next characters.
34                ++i;
35                --j;
36            }
37        }
38      
39        // Convert the character array back into a string and return it.
40        return String.valueOf(characters);
41    }
42}
43

C++ Solution

1#include <string>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to reverse vowels in a given string
7    std::string reverseVowels(std::string str) {
8        // Initialize a simple hash array to mark vowels
9        bool isVowel[128] = {false};
10      
11        // Mark each vowel as true in the hash array
12        for (char c : "aeiouAEIOU") {
13            isVowel[c] = true;
14        }
15      
16        // Initialize two pointers, one at the start and one at the end of the string
17        int left = 0, right = str.size() - 1;
18      
19        // Use a two-pointer approach to find the vowels to be swapped
20        while (left < right) {
21            // Move the left pointer forward until a vowel is found
22            while (left < right && !isVowel[str[left]]) {
23                ++left;
24            }
25          
26            // Move the right pointer backward until a vowel is found
27            while (left < right && !isVowel[str[right]]) {
28                --right;
29            }
30          
31            // If both pointers still have not met or crossed, swap the vowels
32            if (left < right) {
33                std::swap(str[left++], str[right--]);
34            }
35        }
36
37        // Return the string with vowels reversed
38        return str;
39    }
40};
41

Typescript Solution

1function reverseVowels(s: string): string {
2    // Create a set of vowels for easy access
3    const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
4    // Convert the string to an array to manipulate characters
5    const characters = s.split('');
6    // Initialize two pointers
7    let leftPointer = 0;
8    let rightPointer = characters.length - 1;
9
10    // Process the characters until the two pointers meet
11    while (leftPointer < rightPointer) {
12        // Move the left pointer towards the right until it points to a vowel
13        while (leftPointer < rightPointer && !vowels.has(characters[leftPointer])) {
14            leftPointer++;
15        }
16        // Move the right pointer towards the left until it points to a vowel
17        while (leftPointer < rightPointer && !vowels.has(characters[rightPointer])) {
18            rightPointer--;
19        }
20      
21        // Swap the vowels at the left and right pointers
22        [characters[leftPointer], characters[rightPointer]] = [characters[rightPointer], characters[leftPointer]];
23      
24        // Move the pointers closer towards the center
25        leftPointer++;
26        rightPointer--;
27    }
28
29    // Join the characters back to a string and return the result
30    return characters.join('');
31}
32

Time and Space Complexity

Time Complexity

The primary operation of the algorithm is the while loop that scans the string from both ends towards the center. The two nested while loops inside it (for checking whether the characters at the pointers i and j are vowels or not) also contribute to the total time complexity.

On average, each character in the string will be checked at most twice to see if it is a vowel (once for each pointer), which gives us O(2n) time complexity, but when simplified, it is denoted as O(n), where n is the length of the string.

An additional consideration is the reversal operation for vowels which occurs once for each vowel in the string. However, since this is a constant time operation (swapping characters) and is done at most n/2 times (assuming the worst case where all characters are vowels), it does not affect the overall time complexity which remains O(n).

Space Complexity

The space complexity is mainly due to converting the string to a list of characters, which takes O(n) space, where n is the length of the string. No additional data structures are used that grow with the size of the input, so no further space is required.

Thus, the space complexity of the code is O(n) because it needs to store all characters of the input string in a separate list to perform the swapping operation.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫