LeetCode 345 - Reverse Vowels of a String

The problem asks us to reverse only the vowels in a string while leaving all non-vowel characters in their original positions.

leetcodeeasytwo-pointersstring

LeetCode Problem 345

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

Problem Understanding

The problem asks us to reverse only the vowels in a string while leaving all non-vowel characters in their original positions.

A vowel is defined as one of the following characters:

  • a
  • e
  • i
  • o
  • u

The problem also states that vowels may appear in both lowercase and uppercase forms. This means characters like A, E, I, O, and U must also be treated as vowels.

The input is a single string s. The output should be a new string where:

  • Every consonant and non-letter character stays in the same position.
  • Only the vowels swap positions with each other, in reverse order.

For example:

  • Input: "IceCreAm"
  • Vowels encountered from left to right: ['I', 'e', 'e', 'A']
  • Reversed vowel order: ['A', 'e', 'e', 'I']
  • Final string: "AceCreIm"

The constraints are important:

  • The string length can be as large as 3 * 10^5
  • The string contains printable ASCII characters

Because the input can be very large, we need an efficient algorithm. A quadratic time solution could become too slow. This strongly suggests that we should aim for a linear time approach, ideally O(n).

Several edge cases are important to consider:

  • Strings with no vowels, such as "rhythm"
  • Strings consisting entirely of vowels, such as "aeiou"
  • Strings with only one vowel
  • Strings containing uppercase vowels
  • Strings containing symbols or spaces
  • Very large strings near the maximum constraint size

A correct solution must handle all of these efficiently.

Approaches

Brute Force Approach

A straightforward way to solve the problem is:

  1. Traverse the string and collect all vowels into a separate list.
  2. Reverse that vowel list.
  3. Traverse the string again and rebuild the result:
  • If the current character is a vowel, replace it with the next vowel from the reversed list.
  • Otherwise, keep the original character.

This approach works because it explicitly extracts the vowels, reverses their order, and places them back into the string in vowel positions only.

Although this solution is correct, it requires extra passes through the string and additional storage proportional to the number of vowels. While still acceptable for this problem, it is not the most space-efficient approach.

Optimal Approach

The key observation is that we only need to swap vowels from opposite ends of the string.

This naturally suggests a two-pointer strategy:

  • One pointer starts from the left side.
  • Another pointer starts from the right side.
  • Move both pointers inward until they point to vowels.
  • Swap those vowels.
  • Continue until the pointers cross.

This works because the first vowel from the left should become the last vowel in the final result, the second vowel from the left should become the second-last vowel, and so on.

By swapping vowels directly in place, we avoid storing all vowels separately and achieve an efficient linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Extracts and reverses vowels separately
Optimal O(n) O(n) Uses two pointers and swaps vowels directly

The optimal approach still uses O(n) space in Python and Go because strings are immutable, so we must convert the string into a mutable character array.

Algorithm Walkthrough

  1. Create a set containing all vowels, both lowercase and uppercase.

We use a set because membership checks are extremely fast, averaging O(1) time. Since we repeatedly need to ask whether a character is a vowel, a set is the ideal choice. 2. Convert the string into a mutable list of characters.

Strings are immutable in Python and Go, so we cannot modify individual characters directly. Converting to a character array allows efficient swapping. 3. Initialize two pointers:

  • left = 0
  • right = len(characters) - 1

The left pointer scans from the beginning, and the right pointer scans from the end. 4. Move the left pointer forward until it points to a vowel.

Non-vowel characters should remain untouched, so we skip over them. 5. Move the right pointer backward until it points to a vowel.

Again, consonants and other characters stay fixed. 6. When both pointers point to vowels, swap them.

This places the left vowel into its reversed position and the right vowel into its reversed position. 7. Move both pointers inward.

After swapping, those positions are finalized and no longer need processing. 8. Continue until left >= right.

At this point, all vowel swaps are complete. 9. Convert the character array back into a string and return it.

Why it works

The algorithm maintains the invariant that all vowels outside the current pointer range have already been placed in their correct reversed positions.

Each swap exchanges the next unmatched vowel from the left with the next unmatched vowel from the right. Since the pointers move inward symmetrically, the vowel order becomes exactly reversed by the time the pointers meet.

Python Solution

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set("aeiouAEIOU")
        
        characters = list(s)
        
        left = 0
        right = len(characters) - 1
        
        while left < right:
            while left < right and characters[left] not in vowels:
                left += 1
            
            while left < right and characters[right] not in vowels:
                right -= 1
            
            characters[left], characters[right] = (
                characters[right],
                characters[left],
            )
            
            left += 1
            right -= 1
        
        return "".join(characters)

The implementation begins by creating a set of vowels for fast lookup. Both lowercase and uppercase vowels are included so the algorithm correctly handles mixed-case strings.

The string is converted into a list of characters because Python strings cannot be modified in place. This allows efficient swapping operations.

Two pointers are then initialized. The left pointer scans forward looking for vowels, while the right pointer scans backward.

The nested while loops skip non-vowel characters. Once both pointers identify vowels, those vowels are swapped.

After the swap, both pointers move inward because the current vowel positions are now finalized.

Finally, the modified character list is joined back into a string and returned.

Go Solution

func reverseVowels(s string) string {
    vowels := map[byte]bool{
        'a': true,
        'e': true,
        'i': true,
        'o': true,
        'u': true,
        'A': true,
        'E': true,
        'I': true,
        'O': true,
        'U': true,
    }

    chars := []byte(s)

    left := 0
    right := len(chars) - 1

    for left < right {
        for left < right && !vowels[chars[left]] {
            left++
        }

        for left < right && !vowels[chars[right]] {
            right--
        }

        chars[left], chars[right] = chars[right], chars[left]

        left++
        right--
    }

    return string(chars)
}

The Go implementation follows the same algorithmic structure as the Python version.

One important difference is that Go strings are immutable and indexed by bytes. Since the problem guarantees printable ASCII characters, converting the string to []byte is safe and efficient.

A map[byte]bool is used for vowel lookup. This serves the same purpose as the Python set.

Swapping is performed directly on the byte slice, and the final result is converted back into a string before returning.

Worked Examples

Example 1

Input:

s = "IceCreAm"

Initial character array:

['I', 'c', 'e', 'C', 'r', 'e', 'A', 'm']
Step Left Right Left Char Right Char Action Result
Start 0 7 I m Right moves left IceCreAm
1 0 6 I A Swap vowels AceCreIm
2 1 5 c e Left moves right AceCreIm
3 2 5 e e Swap vowels AceCreIm
End 3 4 C r No more swaps AceCreIm

Final output:

"AceCreIm"

Example 2

Input:

s = "leetcode"

Initial character array:

['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']
Step Left Right Left Char Right Char Action Result
Start 0 7 l e Left moves right leetcode
1 1 7 e e Swap vowels leetcode
2 2 6 e d Right moves left leetcode
3 2 5 e o Swap vowels leotcede
End 3 4 t c Stop leotcede

Final output:

"leotcede"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer moves across the string at most once
Space O(n) Character array copy is required because strings are immutable

The time complexity is linear because each character is processed at most once by either the left or right pointer. Even though there are nested loops, the pointers only move forward or backward without revisiting positions.

The space complexity is linear because we create a mutable copy of the string. Aside from that, only a small fixed-size vowel set or map is used.

Test Cases

solution = Solution()

# Provided examples
assert solution.reverseVowels("IceCreAm") == "AceCreIm"  # mixed case vowels
assert solution.reverseVowels("leetcode") == "leotcede"  # standard example

# No vowels
assert solution.reverseVowels("rhythm") == "rhythm"  # unchanged string

# All vowels
assert solution.reverseVowels("aeiou") == "uoiea"  # complete reversal

# Single character
assert solution.reverseVowels("a") == "a"  # single vowel
assert solution.reverseVowels("b") == "b"  # single consonant

# Mixed uppercase and lowercase
assert solution.reverseVowels("Aa") == "aA"  # case-sensitive swap

# Repeated vowels
assert solution.reverseVowels("banana") == "bananaa"[::-1][::-1]  # repeated vowel positions

# Symbols and spaces
assert solution.reverseVowels("h!e l?lo") == "h!o l?le"  # punctuation preserved

# Empty-style edge behavior within constraints
assert solution.reverseVowels("bcdfg") == "bcdfg"  # no vowels at all

# Palindrome vowels
assert solution.reverseVowels("racecar") == "racecar"  # vowels symmetric

# Large repeated input
large_input = "a" * 10000
assert solution.reverseVowels(large_input) == large_input  # stress test
Test Why
"IceCreAm" Validates mixed uppercase and lowercase vowels
"leetcode" Standard example with multiple swaps
"rhythm" Ensures strings without vowels remain unchanged
"aeiou" Validates complete vowel reversal
"a" Smallest vowel-only input
"b" Smallest consonant-only input
"Aa" Confirms uppercase vowels are handled correctly
"banana" Tests repeated vowels
"h!e l?lo" Ensures punctuation and spaces remain fixed
"bcdfg" Another no-vowel scenario
"racecar" Tests symmetric vowel arrangement
Large repeated input Confirms scalability and efficiency

Edge Cases

Strings With No Vowels

An input like "rhythm" contains no vowels at all. A buggy implementation might incorrectly attempt swaps or move pointers out of bounds.

This implementation handles the case safely because both pointers continue skipping characters until they cross. Since no swaps occur, the original string is returned unchanged.

Strings With Only Vowels

An input like "aeiou" requires every character to participate in the reversal. This stresses the correctness of the swapping logic.

The two-pointer method naturally handles this case because every pointer position immediately qualifies as a vowel, so swaps occur directly until the pointers meet.

Uppercase Vowels

Inputs such as "IceCreAm" include uppercase vowels. A common mistake is checking only lowercase vowels.

This implementation avoids that bug by explicitly including both lowercase and uppercase vowels in the lookup set or map.

Strings With Symbols and Spaces

The input may contain printable ASCII characters, not just letters. Characters like spaces, punctuation, and digits must remain untouched.

The algorithm handles this correctly because only characters found in the vowel lookup set are swapped. Every other character is skipped automatically.

Very Large Inputs

The maximum input size is 3 * 10^5, so inefficient algorithms may become too slow.

The two-pointer solution processes each character at most once, guaranteeing linear time performance even for very large strings.