Reverse Vowels of a String - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 2 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: String Manipulation, Two Pointers

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• We need to reverse only the vowels in the string and return the modified string.
• The vowels are 'a', 'e', 'i', 'o', 'u' and their uppercase counterparts 'A', 'E', 'I', 'O', 'U'.

Example 1:
HAPPY CASE
Input: "robin"
Output: "ribon"

Example 2:
Input: "BATgirl"
Output: "BiTgArl"

Example 3:
Input: "batman"
Output: "batman" (no change as there is a single, unique vowel)

Edge Cases:
Empty string input should return an empty string.
A string with no vowels should return the same string.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: The solution to reversing vowels in a string involves using the two-pointers technique. Convert the string to a list to allow in-place modifications, then initialize two pointers at the start and end of the list. Traverse inward, swapping vowels when found, and keep non-vowel characters in place. Finally, convert the modified list back to a string and return it. This approach ensures an efficient reversal of vowels while maintaining the original order of non-vowel characters.

1.Convert the input string to a list to allow mutable operations.
2. Initialize two pointers: left at the start of the list and right at the end of the list.
3. Use a set to store vowels for quick lookup.
4. While left is less than right:
Move left pointer to the right until a vowel is found.
Move right pointer to the left until a vowel is found.
Swap the vowels at the left and right pointers.
Move both pointers inward.
5. Convert the list back to a string and return it.

⚠️ Common Mistakes

• Incorrectly formatting the strings (ensure they match exactly).
• Forgetting to handle characters not listed in the table.

I-mplement

Implement the code to solve the algorithm.

def reverse_vowels(s):
    vowels = set("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
        s_list[left], s_list[right] = s_list[right], s_list[left]
        left += 1
        right -= 1
    
    return ''.join(s_list)