Leetcode – Reverse Vowels of a String Solution in Python

Spread the love

In this extensive article, we will tackle the “Reverse Vowels of a String” problem available on LeetCode. Our primary programming language will be Python due to its simplicity and readability. The article is structured as follows:

Table of Contents

  1. Understanding the Problem Statement
  2. Approach to Solving the Problem
    • Brute Force Method
    • Two Pointers Technique
  3. Code Implementation
  4. Analyzing Time Complexity
  5. Test Cases and Edge Cases
  6. Optimization Techniques
  7. Variations of the Problem
  8. Real-World Applications
  9. Conclusion

Understanding the Problem Statement

The problem can be found on LeetCode under the title “Reverse Vowels of a String.” It requires you to write a function that takes a string s as input and reverses only the vowels of the string. The problem specifies that the vowels are 'a', 'e', 'i', 'o', and 'u' (both lowercase and uppercase).

Example:

Input: "hello"

Output: "holle"

Approach to Solving the Problem

Brute Force Method

A naive approach is to find each vowel’s index in the string and then swap them. However, this method is inefficient, especially for longer strings.

Two Pointers Technique

A better approach is to use the two-pointer technique. This method uses two pointers, one starting from the beginning of the string and the other from the end. These pointers move toward each other. Whenever both pointers point to a vowel, we swap these vowels.

This method is more efficient as it scans the string only once and has a minimal number of swaps.

Let’s dive into the code using the Two Pointers Technique.

def reverseVowels(s: str) -> str:
    # Convert the string to a list for easy manipulation
    s_list = list(s)
    
    # Set of vowels (both lowercase and uppercase)
    vowels = set('aeiouAEIOU')
    
    # Two pointers
    left, right = 0, len(s) - 1
    
    # Loop until the pointers meet
    while left < right:
        # Move the left pointer until a vowel is found
        while left < right and s_list[left] not in vowels:
            left += 1
        
        # Move the right pointer until a vowel is found
        while left < right and s_list[right] not in vowels:
            right -= 1
        
        # Swap the vowels
        s_list[left], s_list[right] = s_list[right], s_list[left]
        
        # Move both pointers towards the center
        left, right = left + 1, right - 1
    
    # Convert the list back to a string and return it
    return ''.join(s_list)

Analyzing Time Complexity

The time complexity of the above algorithm is O(n), where n is the length of the input string. This is because each element is checked at most twice.

Test Cases and Edge Cases

It’s essential to test the algorithm with various inputs, including edge cases, such as an empty string, a string with no vowels, or a string with only vowels.

Optimization Techniques

The algorithm is already quite efficient, but you can make minor improvements, such as using a set to store vowels for faster lookup times.

Variations of the Problem

You can challenge yourself by trying variations of this problem, like reversing only consonants or reversing characters based on different conditions.

Real-World Applications

While reversing vowels in a string is more of an academic problem, the techniques used here, especially the two-pointer technique, are fundamental and can be used in various real-world applications such as data processing, searching, and optimization problems.

Conclusion

The “Reverse Vowels of a String” problem is an excellent exercise for learning basic string manipulation and optimization techniques, such as the two-pointer technique.

Leave a Reply