LeetCode 345: Reverse Vowels of a String Solution in Python – A Step-by-Step Guide

What Is LeetCode 345: Reverse Vowels of a String?

In LeetCode 345: Reverse Vowels of a String, you’re given a string s, and your task is to reverse only the vowels (a, e, i, o, u, both lowercase and uppercase) while keeping all other characters in their original positions. For example, with s = "hello", the result is "holle". This problem tests your ability to manipulate strings selectively, building on basics from LeetCode 344: Reverse String.

Problem Statement

• Input: A string s.
• Output: A string with only its vowels reversed.
• Rules:
• Vowels are a, e, i, o, u (case-insensitive).
• Non-vowel characters stay in place.
• Return the modified string.

Constraints

• 1 <= s.length <= 3 * 10⁵
• s contains printable ASCII characters.

Examples

• Input: "hello"
• Output: "holle" (e ↔ o)
• Input: "leetcode"
• Output: "leotcede" (e ↔ e, e ↔ o)
• Input: "aA"
• Output: "Aa" (a ↔ A)

Understanding the Problem: Swapping the Vowels

To solve LeetCode 345: Reverse Vowels of a String in Python, we need to identify and reverse the vowels in s while preserving the positions of consonants. A naive approach—extracting vowels, reversing them, and rebuilding—uses O(n) extra space, which we can avoid. Instead, we’ll use:

• Best Solution (Two-Pointer): O(n) time, O(1) space—fast and space-efficient.
• Alternative Solution (List-Based): O(n) time, O(n) space—clear but less optimal.

Let’s start with the two-pointer solution, explained in a beginner-friendly way.

Best Solution: Two-Pointer Approach

Why This Is the Best Solution

The two-pointer approach is the top choice for LeetCode 345 because it’s efficient—O(n) time, O(1) space—and elegantly swaps vowels in-place using two pointers moving from the ends inward. It avoids extra storage beyond a few variables, making it both fast and memory-efficient. It’s like a vowel dance where partners swap places—smooth and quick!

How It Works

Think of this as a vowel swapper:

• Step 1: Define Vowels:
• Set of vowels: {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}.
• Step 2: Set Pointers:
• left starts at 0, right at len(s) - 1.
• Step 3: Swap Vowels:
• Move left until vowel, right until vowel.
• Swap if both point to vowels, then move inward.
• Step 4: Stop When Done:
• When left ≥ right, vowels are reversed.
• Step 5: Why It Works:
• Only vowels swap, consonants stay put.
• In-place with minimal space.

It’s like mirroring just the vowels across the string!

Step-by-Step Example

Example: s = "hello"

• Init: s = ["h","e","l","l","o"], left = 0, right = 4
• Step 1: left = 0 (h, not vowel), left = 1 (e), right = 4 (o)
• Swap e ↔ o: s = ["h","o","l","l","e"]
• left = 2, right = 3
• Step 2: left = 2 (l, not vowel), left = 3 (l), right = 3 (l)
• Step 3: left ≥ right, stop
• Result: "holle"

Example: s = "leetcode"

• Init: s = ["l","e","e","t","c","o","d","e"], left = 0, right = 7
• Step 1: left = 1 (e), right = 7 (e), no swap, left = 2, right = 6
• Step 2: left = 2 (e), right = 6 (d), right = 5 (o)
• Swap e ↔ o: s = ["l","e","o","t","c","e","d","e"]
• left = 3, right = 4
• Step 3: left = 5 (e), right = 4 (c), stop
• Result: "leotcede"

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def reverseVowels(self, s: str) -> str:
        # Define vowels
        vowels = set('aeiouAEIOU')

        # Convert string to list for in-place modification
        s_list = list(s)
        left, right = 0, len(s) - 1

        # Swap vowels from ends inward
        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

        # Convert back to string
        return ''.join(s_list)

• Line 3: Set of vowels (case-insensitive).
• Lines 6-7: Convert string to list, set pointers.
• Lines 10-16: While loop:
• Move left until vowel.
• Move right until vowel.
• Swap vowels, advance pointers.
• Line 19: Join list back to string.
• Time Complexity: O(n)—traverse string once.
• Space Complexity: O(1)—excluding input/output (vowels set is constant).

This is like a vowel-swapping maestro—fast and sleek!

Alternative Solution: List-Based Approach

Why an Alternative Approach?

The list-based approach—O(n) time, O(n) space—extracts vowels into a separate list, reverses them, and rebuilds the string. It’s more intuitive for understanding the process but uses O(n) extra space, making it less efficient. It’s like sorting vowels separately—clear but bulkier!

How It Works

Extract and rebuild:

• Step 1: Collect vowels and their positions.
• Step 2: Reverse the vowel list.
• Step 3: Rebuild string, replacing vowels.

Step-by-Step Example

Example: s = "hello"

• Step 1: Vowels = [(e,1), (o,4)]
• Step 2: Reverse = [(o,4), (e,1)]
• Step 3: Rebuild: "h" + "o" + "l" + "l" + "e" = "holle"
• Result: "holle"

Code for List-Based Approach

Copy codeclass Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        vowel_list = [(char, i) for i, char in enumerate(s) if char in vowels]

        # Reverse vowels
        vowel_list = vowel_list[::-1]

        # Rebuild string
        result = list(s)
        for char, i in vowel_list:
            result[i] = char

        return ''.join(result)

• Time Complexity: O(n)—traverse and rebuild.
• Space Complexity: O(n)—vowel list and result array.

It’s a vowel-sorting rebuilder—vivid but heavy!

Comparing the Two Solutions

• Two-Pointer (Best):
• Pros: O(n) time, O(1) space, in-place and fast.
• Cons: Pointer logic less obvious.
• List-Based (Alternative):
• Pros: O(n) time, O(n) space, straightforward.
• Cons: Extra space usage.

Two-pointer wins for efficiency.

Additional Examples and Edge Cases

• "a": "a".
• "b": "b".
• "AeIoU": "UoIeA".

Both handle these, but two-pointer is optimal.

Complexity Breakdown

• Two-Pointer: Time O(n), Space O(1).
• List-Based: Time O(n), Space O(n).

Two-pointer is the clear choice.

Key Takeaways

• Two-Pointer: Swap in place—efficient!
• List-Based: Extract and rebuild—clear!
• Python: Strings and sets shine—see [Python Basics](/python/basics).
• Vowels: Selective reversal rocks.

Final Thoughts: Flip the Vowels

LeetCode 345: Reverse Vowels of a String in Python is a fun string manipulation challenge. The two-pointer solution offers speed and elegance, while the list-based approach provides a tangible baseline. Want more string fun? Try LeetCode 344: Reverse String or LeetCode 541: Reverse String II. Ready to swap? Head to Solve LeetCode 345 on LeetCode and reverse those vowels today!