[Google Interview] Reverse Vowels In A String In Python

by

[toc]

Company Tags: Google, Amazon, Facebook

As reported by various programmers, this is one of the frequently asked questions in the Google interview. If this question was asked in your interview, would you be able to solve it optimally?

Problem Statement

Given a string s, reverse only all the vowels in the string and return it. The vowels in English are ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’.

Note: The vowels do not include the alphabet “y“.

Constraints
◈ 1 <= s.length <= 3*105
◈ s consist of printable ASCII characters.

Examples

Let’s have a look at some examples to improve our understanding of this problem.

Example 1:
Input: s = "Eunoia"
Output: "ainouE"
Explanation: The string consists of all alphabets in English. So it is simply a case of reversing the entire string here.

Example 2:
Input: s = "Finxter"
Output: "Fenxtir"
Explanation: The vowels in this string are 'i' and 'e'. The position of these vowels have been swapped to display the output.

Example 3:
Input: s = "hellOO"
Output: "hOllOe"
Explanation: The position of vowels 'O' and 'e' have been swapped in this case.

Example 4:
Input: s = "python3.6"
Output: "python3.6"
Explanation: This string has no vowel. So it remains unchanged.

Example 5:
Input: s = "UAE"
Output: "EAU"
Explanation: The position of vowels 'U' and 'E' have been swapped in this case.

Now that you have a clear picture of the problem let’s dive into the solutions.

❖ Method 1: Using A Python List As A Stack

Approach: As the question asks you to reverse only the vowels, the idea of this approach is to use a Python list as a stack data structure and put the vowels in the stack. By doing this, you can later replace the top of the stack that contains the rightmost vowel with the vowel at the left end of the string. 

The stack data structure follows the approach of LIFO (Last In First Out) or FILO (First In Last Out) to perform operations on its elements. You can implement this property of stack using a list in Python to solve this problem.

Quick Recap: The list.pop() method removes and returns the last element from an existing list. The list.pop(index) method with the optional argument index removes and returns the element at the position index.

Related Article: Python List pop()

Algorithm

  1. First, store all the vowels of the English alphabet in a separate list and simultaneously create another empty list.
  2. In the first iteration, for every character in the string, if the character is present in the list containing all the vowels, append it in the empty stack.
  3. If the character is not present in the list containing the vowels, add it to the new string else add the character from the top of the stack to the next string.
  4. Finally, return the new string.

Let’s implement the algorithm as a code:

def rev_vowels(s):
    vow = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
    st = []
    new_s = ''
    for v in s:
        if v in vow:
            st.append(v)
    for v in s:
        if v in vow:
            new_s = new_s + st.pop()
        else:
            new_s = new_s + v
    return new_s

Test Case Analysis: Let’s run this code on our examples to check if it works:

# Example 1
s = "Eunonia"
print(rev_vowels(s))
# ainouE

# Example 2
s = "Finxter"
print(rev_vowels(s))
# Fenxtir

# Example 3
s = "hellOO"
print(rev_vowels(s))
# hOllOe

# Example 4
s = "python3.6"
print(rev_vowels(s))
# python3.6

# Example 5
s = "UAE"
print(rev_vowels(s))
# EAU

Yeah! It passed all the test cases.

Complexity Analysis

  • Time Complexity: As you have to traverse the string twice, the time complexity of this method will be O(n) + O(n) = O(2n) ~ O(n).
  • Space Complexity: In the worst-case scenario, all the characters in the strings are vowels. (Refer to example 5) In this case, the list will contain all the characters and hence the space complexity will be O(n).

Discussion: In this method, we have traversed the entire array in every case. Although we know that we only have to update the carry when the number is 9 else it remains 0. So, is there a possible solution where we can update the value in the original array itself without creating a whole new array? That will be a better solution as we can terminate the process when the digit becomes less than 9.

❖ Method 2: Using Two Pointers

Approach: Another way of approaching this problem is to use two pointers (i and j) at the start and end of the given string. You have to check if the character is a vowel or not. If yes, you have to swap both the values with each other with the help of the start and end pointers.

Now let’s have a look at the algorithm:

Note: As Python strings are immutable you cannot swap the character directly. You have to create a list (Python lists are mutable) to support swapping. While returning this list, you can use the join() method.

Algorithm:

  1. Initialize two variables i = 0 and j = length(s)-1 that will point towards the start and end of the string. Thus, i and j represent the two pointers here.
  2. While i is less than j, run a loop that will check whether the current character is a vowel or not.
  3. Inside the loop, you have to execute two more loops that will move the pointers so that they point at the vowels.
  4. Swap the values pointed by i and j. To carry on the process of checking for vowels in the string and then swapping them with the help of the pointers shift the pointer i towards the right while shift the pointer j towards the left.
  5. Finally, return the new string.

The following illustration will help you to understand the above algorithm.

Explanation: The given string in this example is FINXTER. The start pointer keeps shifting towards the right while the end ponter shifts towards the left. As soon as a vowel is found at the respective positions/indexes the characters (vowels) are swapped and each pointer continues shrinking. Finally, when the end pointer points to an index that is lesser than the value of the index pointed by the start pointer, the iteration stops and the list is converted to a string as an output. In this example the vowels ‘I’ and ‘E’ get swapped and finally when the end pointer (denoted in grey) points at the third index that has the element ‘X’ and the start pointer (denoted in black) points at the fourth index that has the element ‘T’ , you have to convert the list into a string with the help of the join() method and return it as an output.

Let’s implement the algorithm as a Python code:

def rev_vowels(s):
    vow = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
    new_s = list(s)
    i, j = 0, len(s) - 1
    while i <= j:
        while i < j and s[i] not in vow:
            i = i + 1
        while i < j and s[j] not in vow:
            j = j - 1
        if i > j:
            break
        new_s[i], new_s[j] = new_s[j], new_s[i]
        i = i + 1
        j = j - 1
    return ''.join(new_s)

Let’s try this on our test cases:

# Example 1
s = "Eunonia"
print(rev_vowels(s))
# ainouE

# Example 2
s = "Finxter"
print(rev_vowels(s))
# Fenxtir

# Example 3
s = "hellOO"
print(rev_vowels(s))
# hOllOe

# Example 4
s = "python3.6"
print(rev_vowels(s))
# python3.6

# Example 5
s = "UAE"
print(rev_vowels(s))
# EAU

Hurrah! It passed all the test cases.

Complexity Analysis

  • Time Complexity: In this approach, the string is traversed only once. Hence the time complexity is O(n).
  • Space Complexity: The space complexity of this method will be O(n) as we have to create a list (Python strings are immutable) to store the string characters in order to swap the values.

❖ Method 3: Using Regular Expressions

Not many programmers are very comfortable with Python regular expressions. But once you master the art of using the regex module it renders you an extremely powerful tool to solve complex problems with ease.

A Quick Recap:

re.findall() Visual Explanation
read more here:- “Python re.findall() – Everything You Need to Know”

Now let’s have a look, how you can use regular expressions to solve this problem.

import re


def rev_vowels(s):
    vowels = re.findall('(?i)[aeiou]', s)
    return re.sub('(?i)[aeiou]', lambda m: vowels.pop(), s)

Test Case Analysis:

# Example 1
s = "Eunonia"
print(rev_vowels(s))
# ainouE

# Example 2
s = "Finxter"
print(rev_vowels(s))
# Fenxtir

# Example 3
s = "hellOO"
print(rev_vowels(s))
# hOllOe

# Example 4
s = "python3.6"
print(rev_vowels(s))
# python3.6

# Example 5
s = "UAE"
print(rev_vowels(s))
# EAU

You can also solve this problem in a single line as shown below (probably not the smartest idea to come up with during an interview ?).

import re


def rev_vowels(s):
    return re.sub('(?i)[aeiou]', lambda m, v=re.findall('(?i)[aeiou]', s): v.pop(), s)

Google, Facebook, and Amazon engineers are regular expression masters. If you want to become one as well, check out our new book: The Smartest Way to Learn Python Regex (Amazon Kindle/Print, opens in new tab).

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

? Post Credits: Shubham Sayon and Rashi Agarwal

Recommended: Finxter Computer Science Academy

  • One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
  • So, do you want to master the art of web scraping using Python’s BeautifulSoup?
  • If the answer is yes – this course will take you from beginner to expert in Web Scraping.
Join the Web Scraping with BeautifulSoup Masterclass now, and master it by tomorrow!