Jobs

Interviews

Discussions

Reverse Vowels of a String

Easy

Google

3 views

Topics:

StringsTwo Pointers

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 = "IceCreAm"

Output: "AceCreIm"

Explanation:

The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".

Example 2:

Input: s = "leetcode"

Output: "leotcede"

Constraints:

1 <= s.length <= 3 * 10⁵
s consist of printable ASCII characters.

Reverse Vowels of a String

Easy

Google

3 views

Topics:

StringsTwo Pointers

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 = "IceCreAm"

Output: "AceCreIm"

Explanation:

The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".

Example 2:

Input: s = "leetcode"

Output: "leotcede"

Constraints:

1 <= s.length <= 3 * 10⁵
s consist of printable ASCII characters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input string guaranteed to be ASCII, or can it contain Unicode characters?
Should the case of the vowels be preserved (e.g., 'E' swapping with 'a' resulting in 'eA'), or should I treat all vowels as lowercase during the swap?
What should I return if the input string is null or empty?
Is the definition of 'vowel' strictly 'a', 'e', 'i', 'o', 'u' (and their uppercase versions), or should 'y' be considered a vowel?
If the string contains only vowels, should I reverse the entire string?

Brute Force Solution

Approach

The brute force method for reversing vowels in a string looks at each character one by one. Whenever it finds a vowel, it stores the vowel. Then, it goes through the string again and replaces the vowels in reverse order from how they appeared originally.

Here's how the algorithm would work step-by-step:

First, we'll scan through the whole string.
As we go, every time we find a vowel (a, e, i, o, or u), we'll save it for later.
Once we've gone through the entire string, we'll have a collection of all the vowels that were in the string.
Now, we go through the original string again, from the beginning.
This time, when we find a vowel, we'll replace it with the last vowel we saved.
After replacing the vowel, we'll remove that last vowel from our saved collection so we don't use it again.
We repeat this process until we've gone through the entire original string, replacing each vowel with the next vowel from our saved collection in reverse order.
At the very end, we'll have a modified version of the original string where all the vowels have been reversed.

Code Implementation

def reverse_vowels_of_a_string_brute_force(input_string):
    vowels_found = []

    # Collect all vowels from the input string
    for char in input_string:
        if char in 'aeiouAEIOU':
            vowels_found.append(char)

    string_as_list = list(input_string)

    vowel_index = len(vowels_found) - 1

    # Replace vowels in the string with vowels from the end of our list
    for index in range(len(string_as_list)):
        if string_as_list[index] in 'aeiouAEIOU':

            # Replace vowel with one from list in reverse order
            string_as_list[index] = vowels_found[vowel_index]
            vowel_index -= 1

    return "".join(string_as_list)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string of length n once to identify and store all vowels. Then, it iterates through the string again (another n operations) to replace vowels with the stored vowels in reverse order. Therefore, we have two sequential passes through the string, resulting in 2n operations. This simplifies to O(n).

Space Complexity

O(N) – The provided solution stores all vowels encountered in the input string in a separate collection. In the worst-case scenario, the input string could consist entirely of vowels. This means the auxiliary space required to store the vowels grows linearly with the length of the input string, N, where N is the length of the input string. Therefore, the space complexity is O(N).

Optimal Solution

Approach

To efficiently reverse only the vowels in a string, we can use a two-pointer approach. We'll have one pointer at the beginning and one at the end, moving towards each other, swapping vowels as we find them.

Here's how the algorithm would work step-by-step:

Set up two markers: one at the beginning of the string and one at the end.
Move the beginning marker forward until you find a vowel.
Move the ending marker backward until you find a vowel.
If the beginning marker is still before the ending marker, swap the vowels at those two spots.
Move both markers again: beginning marker forwards and ending marker backwards.
Keep doing this until the two markers meet in the middle or cross over each other.
The string will now have the vowels reversed while keeping the other letters in place.

Code Implementation

def reverse_vowels(input_string):
    vowels = "aeiouAEIOU"
    string_list = list(input_string)
    start_index = 0
    end_index = len(input_string) - 1

    while start_index < end_index:
        # Find the next vowel from the start.
        while start_index < end_index and string_list[start_index] not in vowels:
            start_index += 1

        # Find the next vowel from the end.
        while end_index > start_index and string_list[end_index] not in vowels:
            end_index -= 1

        # Ensure pointers haven't crossed.
        if start_index < end_index:

            # Swap the vowels.
            string_list[start_index], string_list[end_index] = string_list[end_index], string_list[start_index]

            # Move to the next positions.
            start_index += 1
            end_index -= 1

    return "".join(string_list)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses two pointers, one starting at the beginning of the string and the other at the end. Each pointer moves towards the center, at most traversing the entire string once. The primary operation is checking if a character is a vowel and potentially swapping characters. Therefore, the number of operations is directly proportional to the length of the string (n), leading to a time complexity of O(n).

Space Complexity

O(N) – The provided solution modifies the string in-place, so it may appear to use constant space. However, because strings are immutable in many common programming languages, we need to convert it to a mutable data structure such as a list (or character array) to perform in-place modification. Creating this list takes O(N) space, where N is the length of the input string. The algorithm then uses a constant number of extra variables (two pointers) during the reversal process, which contributes O(1) space. Therefore, the dominant factor is the creation of the mutable list, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty string input	Return null or an empty string respectively to handle invalid input.
String with no vowels	Return the original string as no vowels need to be reversed.
String with only one vowel	Return the original string as there's nothing to reverse.
String with only vowels	Reverse the entire string as it only contains vowels.
String with mixed case vowels	Treat uppercase and lowercase vowels equally during identification and reversal.
String with non-ASCII characters	Ensure the vowel check considers Unicode vowels beyond basic ASCII.
Very long string (potential performance bottleneck)	Use a two-pointer approach to optimize for O(n) time complexity.
String containing only consonants	The algorithm should return the original string, as no vowels exist to reverse.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input string guaranteed to be ASCII, or can it contain Unicode characters?
Should the case of the vowels be preserved (e.g., 'E' swapping with 'a' resulting in 'eA'), or should I treat all vowels as lowercase during the swap?
What should I return if the input string is null or empty?
Is the definition of 'vowel' strictly 'a', 'e', 'i', 'o', 'u' (and their uppercase versions), or should 'y' be considered a vowel?
If the string contains only vowels, should I reverse the entire string?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, we'll scan through the whole string.
As we go, every time we find a vowel (a, e, i, o, or u), we'll save it for later.
Once we've gone through the entire string, we'll have a collection of all the vowels that were in the string.
Now, we go through the original string again, from the beginning.
This time, when we find a vowel, we'll replace it with the last vowel we saved.
After replacing the vowel, we'll remove that last vowel from our saved collection so we don't use it again.
We repeat this process until we've gone through the entire original string, replacing each vowel with the next vowel from our saved collection in reverse order.
At the very end, we'll have a modified version of the original string where all the vowels have been reversed.

Code Implementation

def reverse_vowels_of_a_string_brute_force(input_string):
    vowels_found = []

    # Collect all vowels from the input string
    for char in input_string:
        if char in 'aeiouAEIOU':
            vowels_found.append(char)

    string_as_list = list(input_string)

    vowel_index = len(vowels_found) - 1

    # Replace vowels in the string with vowels from the end of our list
    for index in range(len(string_as_list)):
        if string_as_list[index] in 'aeiouAEIOU':

            # Replace vowel with one from list in reverse order
            string_as_list[index] = vowels_found[vowel_index]
            vowel_index -= 1

    return "".join(string_as_list)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Set up two markers: one at the beginning of the string and one at the end.
Move the beginning marker forward until you find a vowel.
Move the ending marker backward until you find a vowel.
If the beginning marker is still before the ending marker, swap the vowels at those two spots.
Move both markers again: beginning marker forwards and ending marker backwards.
Keep doing this until the two markers meet in the middle or cross over each other.
The string will now have the vowels reversed while keeping the other letters in place.

Code Implementation

def reverse_vowels(input_string):
    vowels = "aeiouAEIOU"
    string_list = list(input_string)
    start_index = 0
    end_index = len(input_string) - 1

    while start_index < end_index:
        # Find the next vowel from the start.
        while start_index < end_index and string_list[start_index] not in vowels:
            start_index += 1

        # Find the next vowel from the end.
        while end_index > start_index and string_list[end_index] not in vowels:
            end_index -= 1

        # Ensure pointers haven't crossed.
        if start_index < end_index:

            # Swap the vowels.
            string_list[start_index], string_list[end_index] = string_list[end_index], string_list[start_index]

            # Move to the next positions.
            start_index += 1
            end_index -= 1

    return "".join(string_list)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return null or an empty string respectively to handle invalid input.
String with no vowels	Return the original string as no vowels need to be reversed.
String with only one vowel	Return the original string as there's nothing to reverse.
String with only vowels	Reverse the entire string as it only contains vowels.
String with mixed case vowels	Treat uppercase and lowercase vowels equally during identification and reversal.
String with non-ASCII characters	Ensure the vowel check considers Unicode vowels beyond basic ASCII.
Very long string (potential performance bottleneck)	Use a two-pointer approach to optimize for O(n) time complexity.
String containing only consonants	The algorithm should return the original string, as no vowels exist to reverse.