#345

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Reverse Vowels of a String

Reverse Vowels of a String uses a two-pointer approach to reverse the vowels in a string while leaving the consonants intact.

two pointers string

Problem Statement

Given a string s, your task is to reverse only the vowels in the string and return the modified string. The vowels are defined as 'a', 'e', 'i', 'o', and 'u', and can appear in both lowercase and uppercase. You should return the new string with the vowels reversed, while keeping the positions of consonants unchanged.

For example, with the string s = "IceCreAm", the vowels 'I', 'e', 'e', and 'A' are reversed to become 'A', 'e', 'I', and 'a' respectively, resulting in the output "AceCreIm".

Examples

Example 1

Input: s = "IceCreAm"

Output: "AceCreIm"

The vowels in s are ['I', 'e', 'e', 'A'] . On reversing the vowels, s becomes "AceCreIm" .

Example 2

Input: s = "leetcode"

Output: "leotcede"

Example details omitted.

Constraints

1 <= s.length <= 3 * 105
s consist of printable ASCII characters.

Solution Approach

Two-Pointer Approach

Start with two pointers, one at the beginning and one at the end of the string. Move the left pointer forward and the right pointer backward until both pointers point to vowels. Swap these vowels and continue the process until the pointers cross each other.

Skip Non-Vowel Characters

Ensure that each pointer skips over non-vowel characters. This can be done efficiently by checking if the character at each pointer is a vowel before moving it. If it's not a vowel, simply increment or decrement the respective pointer.

In-place Modification

Modify the string in-place to avoid extra space usage. Strings are immutable in many languages, so this approach requires converting the string into a list of characters. After processing the vowels, the list can be joined back into a string for the final result.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) since each character is visited at most twice—once by each pointer. The space complexity is O(1) if we modify the string in-place, or O(n) if we use a list to handle string manipulation.

What Interviewers Usually Probe

Look for proficiency with the two-pointer technique and how candidates manage pointer movement.
Ensure the candidate accounts for both uppercase and lowercase vowels during swaps.
Assess the candidate's ability to optimize for space complexity, especially when handling large input sizes.

Common Pitfalls or Variants

Common pitfalls

Failing to skip non-vowel characters efficiently can lead to unnecessary checks and inefficiency.
Not handling both uppercase and lowercase vowels correctly might result in incorrect outputs.
Attempting to reverse vowels without properly converting the string to a mutable data structure could cause errors in languages where strings are immutable.

Follow-up variants

Reverse the vowels only in a substring, not the entire string.
Add a limit to the number of vowels that can be reversed, such as reversing only the first 3 vowels.
Consider a case where only specific vowels (e.g., 'a' and 'o') are reversed, not all vowels.

FAQ

What is the two-pointer approach in the Reverse Vowels of a String problem?

The two-pointer approach uses one pointer starting from the beginning of the string and another from the end. These pointers move towards each other, swapping vowels until they cross.

How do you handle vowels in both lowercase and uppercase?

You treat both lowercase and uppercase vowels ('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U') as valid vowels, ensuring the case is respected during swapping.

Can I use extra space in the Reverse Vowels of a String problem?

While the problem can be solved in-place with O(1) space, using extra space for easier string manipulation is acceptable, especially for readability, which would increase space complexity to O(n).

Why is the two-pointer approach efficient for this problem?

The two-pointer approach is efficient because it scans the string in linear time, only swapping vowels while leaving consonants untouched. This reduces the time complexity to O(n).

How can GhostInterview help with Reverse Vowels of a String?

GhostInterview provides insights into optimizing both time and space complexity while practicing key techniques such as two-pointer scanning, ensuring a thorough solution.

terminal

Solution

Solution 1: Two Pointers

We can use two pointers $i$ and $j$, initially pointing to the start and end of the string respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Continue Practicing

#344 reverse string #392 is subsequence #443 string compression