How do you solve Reverse Vowels of a String on LeetCode?

Reverse Vowels of a String (LeetCode #345) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using two pointers can significantly reduce time complexity.

What is the brute force solution for Reverse Vowels of a String?

The brute force approach for Reverse Vowels of a String is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves identifying all the vowels in the string, storing them, and then replacing them in reverse order. This is straightforward but inefficient as it requires multiple passes over the string. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Reverse Vowels of a String?

Reverse Vowels of a String uses the following concepts: Two Pointers, String. The recommended patterns to study are: Two Pointers, String Manipulation.

What are the interview tips for Reverse Vowels of a String?

Explain your thought process clearly while coding. Consider edge cases like strings with no vowels. Practice the two-pointer technique as it's commonly used in string manipulation problems.

What are common mistakes when solving Reverse Vowels of a String?

Not handling both uppercase and lowercase vowels. Using unnecessary extra space when a two-pointer approach is possible.

#345

Reverse Vowels of a String

Easy

Two PointersStringTwo PointersString Manipulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses the two-pointer technique to reverse the vowels in a single pass through the string. This is efficient because we only traverse the string once, making it faster.

⚙️

Algorithm

5 steps

1Step 1: Initialize two pointers, one at the start and one at the end of the string.
2Step 2: Move the left pointer to the right until a vowel is found.
3Step 3: Move the right pointer to the left until a vowel is found.
4Step 4: Swap the vowels at the two pointers and move both pointers towards the center.
5Step 5: Repeat until the pointers meet.

solution.py15 lines

1# Full working Python code
2
3def reverseVowels(s):
4    s_list = list(s)
5    left, right = 0, len(s) - 1
6    vowels = set('aeiouAEIOU')
7    while left < right:
8        while left < right and s_list[left] not in vowels:
9            left += 1
10        while left < right and s_list[right] not in vowels:
11            right -= 1
12        s_list[left], s_list[right] = s_list[right], s_list[left]
13        left += 1
14        right -= 1
15    return ''.join(s_list)

ℹ

Complexity note: The time complexity is O(n) because we traverse the string only once, and the space complexity is O(1) as we are not using any additional data structures that grow with input size.

1Using two pointers can significantly reduce time complexity.
2Understanding vowel identification is crucial for the problem.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.