How to Reverse Vowels in a String?

Reversing vowels in a string is a popular coding problem that tests a developer's ability to manipulate strings and implement effective algorithms. This task requires both a keen eye for detail and an understanding of string manipulation techniques. Let's explore this topic, including potential interview questions and examples of how to approach answering them.

Understanding the Problem

The goal is to reverse only the vowels in a given string while keeping the consonants and spaces in their original positions. Vowels are typically defined as 'a', 'e', 'i', 'o', 'u' (case insensitive).

Example

For example, given the input string "hello", the output should be "holle". For the input "Leap Year", the output should be "Leep Yaar".

The Algorithm

The simplest approach to reverse vowels in a string involves the following steps:

1. Identify Vowels: Create a list of characters that represent vowels.
2. Extract Vowels: Traverse the string and collect all the vowels in the order they appear.
3. Reverse the Vowels: Reverse the list of vowels collected.
4. Rebuild the String: Replace the vowels in the original string with the reversed vowels.

Here's a basic outline of the algorithm in code:

PythonCopy code
def reverse_vowels(s: str) -> str:
    vowels = 'aeiouAEIOU'
    s_list = list(s)
    left, right = 0, len(s) - 1
    
    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)

Example Interview Questions

1. Basic Question:

   • Q: "Can you write a function to reverse the vowels in the string 'hello world'?"
   • A: "Yes, I would first identify the vowels in the string, gather them in a list, reverse that list, and then reconstruct the string by replacing the original vowels with those in the reversed list."

2. Complex Case:

   • Q: "How would you handle a string that contains numbers or special characters?"
   • A: "The logic for identifying vowels remains unchanged. The algorithm should skip over numbers and special characters while processing the string. Here's how I would modify the code slightly to handle this."

3. Performance:

   • Q: "What is the time complexity of your solution?"
   • A: "The time complexity is O(n), where n is the length of the string. Each character is processed at most twice, once when the left pointer moves right and once when the right pointer moves left."

4. Edge Cases:

   • Q: "How does your solution handle empty strings or strings with no vowels?"
   • A: "My solution will return the string as is. For an empty string, it will simply return an empty string, and for a string without vowels, it will return the original string without modification."

5. Test Cases:

   • Q: "Can you provide some test cases to validate your solution?"
   • A: "Certainly! Here are a few test cases:
     • Input: 'abcdefg', Output: 'ebcdfg'
     • Input: 'aA', Output: 'Aa'
     • Input: '12345', Output: '12345' (no change)
     • Input: '', Output: '' (empty string remains empty)
     • Input: 'Tutorial, nice to meet you!', Output: 'Tutearial, nica to meet yau!'"

Reversing vowels in a string is a straightforward yet effective way to assess a developer's problem-solving skills. By practicing different scenarios and variations of this problem, a developer can significantly improve their understanding of string manipulation and algorithm optimization during interviews.