Leet code 345. Reverse Vowels of a String

Optimize to get 99% in Python: Detail explanation!

Try it yourself! Leet code link

Intuition

As an engineer who did not graduate from a Computer Science program, I understand that some Python users may not be familiar with algorithms and data structures. Optimizing time and space complexity can be challenging. This LeetCode question is a great example to illustrate these concepts!

Two major concepts used here are:

1. Two Pointers
2. HashMap or set() function

For those unfamiliar with data structures, the initial intuition might be to read through the entire string from start to end and then try to change the vowels. But why read data sequentially when you can start from both ends?

This is where the Two Pointer technique comes in, a widely used approach to solve problems like this.

Two Pointers:

• Initialize two pointers at the start and end of the string.
• Move the pointers inward: if a pointer does not point to a vowel, move it to the next/previous character.
• When the pointers meet or cross, you have scanned the entire string.

Next, how does the computer recognize a vowel? Python provides a built-in function called in for checking if a character is in a string:

my_string = "apple"
if "e" in my_string:
  print(True)

This works but is inefficient because the in operation checks each character in sequence, leading to O(n) time complexity.

We can improve this with the set() function! Using set() leverages Hash mapping function, allowing for O(1) time complexity for membership tests. Here’s a comparison:

my_set = set("apple")
if "e" in my_set:
  print(True)

The set() function is more efficient due to its different data structure compared to a simple list. Each time a value is added to a set, it is processed by a hash function, which generates a unique hashed value. The data is then stored at the position corresponding to this hashed value.

If you have difficulty understanding, think of it as storing data at:

set[hashed_value] = data.

Therefore, when checking if ‘e’ is inside the set, the operation only needs to execute once: calculate hash(‘e’) and check if there is data at that position. This is much more efficient than scanning through all the data in a list.

Now you know the key concept to build an optimal solution!

Approach

• Declare a set() to store the vowels
• Declare two pointer check if the pointer are at vowel, if not, move next/previous
• If two pointer are at vowel, swap them.
• Be cautious when changing the vowels. There is no replace function for the string data type, so we need to use a list instead of a string.

Additionally, you might consider using concatenation to achieve replacement, but this costs another O(N) due to the immutability of strings. For example:

s1 = "Hello"
s2 = " World"
s1 = s1 + s2

When concatenating two strings, Python creates a new string space, then copies s1 and s2 into that space, rather than linking the two strings. Concatenation in Python is more complex to implement and is generally less efficient.

Complexity

Time complexity:

O(N)

Using the set() function provides O(1) time complexity for each membership test. Scanning through the string is O(N), and converting the string into a list also costs O(N).

Space complexity:

O(N)

We allocate space for the vowels and convert the string into a list, resulting in O(N) space complexity without additional overhead.

Code

class Solution:
    def reverseVowels(self, s: str) -> str:
        # declare a `set()` store the vowels
        vowels = set('aeiouAEIOU')
        # declare two pointer
        left, right = 0, len(s)- 1
        # Chage data type to list, convienient for swap vowel
        s = list(s)
        while left < right:
            # As the picture shown above, the left pointer is not point at a vowel, we move to next one.
            while left < right and s[left] not in vowels:
                left += 1
            # If the right pointer not point to vowel, move previous. Notice it is minus.
            while left < right and s[right] not in vowels:
                right -= 1
            # Both pointer point at vowel, swap it.
            if left < right and s[left] in vowels and s[right] in vowels:
                s[left], s[right] = s[right], s[left]  # Swap the vowels
                left += 1
                right -= 1
                
        return ''.join(s)  # Convert list back to string