Solution: Reverse Vowels

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Reverse Vowels

Table of Contents

Contents are not accessible

Problem Statement

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Example 1:

Input: s= "hello"
Output: "holle"

Example 2:

Input: s= "AEIOU"
Output: "UOIEA"

Example 3:

Input: s= "DesignGUrus"
Output: "DusUgnGires"

Constraints:

1 <= s.length <= 3 * 10<sup>5</sup>
s consist of printable ASCII characters.

Solution

We need to reverse the vowels in a string, keeping the positions of the consonants and other characters intact. We can use the two-pointer technique to traverse the string from both ends simultaneously. Whenever a vowel is encountered at both ends, we will swap them. The process will continue until the two pointers meet in the middle.

Walk through of the algorithm

Now let's walk through the code:

We first create a static string "vowels" that contains all lowercase and uppercase vowels. This is used for checking whether a character in the input string is a vowel.
The reverseVowels method accepts a string 's' as an argument. The first and last pointers are initialized to the start and end of the string, respectively.
We convert the input string 's' to a character array 'array' to allow easy manipulation of individual characters.
We enter a while loop that continues while 'first' is less than 'last'.
Inside the while loop, we have two nested while loops:
- The first nested while loop keeps incrementing the 'first' pointer until it points to a vowel or 'first' is no longer less than 'last'.
- The second nested while loop keeps decrementing the 'last' pointer until it points to a vowel or 'first' is no longer less than 'last'.
Once we've found a vowel at both the 'first' and 'last' pointers, we swap these vowels.
After the swap, we increment the 'first' pointer and decrement the 'last' pointer, and continue to the next iteration of the outer while loop.
After exiting the while loop, we convert the character array back to a string and return it as the result.

Code

Here is the code for this algorithm:

Python3

. . . .

Complexity Analysis

Time Complexity

Two-pointer traversal: The algorithm uses two pointers (first and last) to traverse the string from both ends, swapping vowels when they are found.
Linear scan: Each character in the string is checked at most once, resulting in a linear scan of the string.
Vowel check: Checking if a character is a vowel using vowels.indexOf() is a constant time operation, $O(1)$ , because the string of vowels is fixed in length (10 characters).

Overall time complexity: $O(N)$ , where N is the length of the input string.

Space Complexity

Character array: The algorithm converts the input string into a character array, which requires $O(N)$ space, where N is the length of the input string.
Additional variables: The algorithm uses a few extra variables (first, last, and temp), which require constant space, $O(1)$ .

Overall space complexity: $O(N)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible