# Reverse Vowels of a String
**Difficulty:** EASY
[External](https://leetcode.com/problems/reverse-vowels-of-a-string)
Canonical: https://scaleengineer.com/dsa/problems/reverse-vowels-of-a-string
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Accolite](https://scaleengineer.com/companies/accolite), [Zoho](https://scaleengineer.com/companies/zoho), [Twitch](https://scaleengineer.com/companies/twitch), [USAA](https://scaleengineer.com/companies/usaa)
---
## Problem
Given a string `s`, reverse only all the vowels in the string and return it.

The vowels are `'a'`, `'e'`, `'i'`, `'o'`, and `'u'`, and they can appear in both lower and upper cases, more than once.

**Example 1:**

**Input:** s = "IceCreAm"

**Output:** "AceCreIm"

**Explanation:**

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

**Example 2:**

**Input:** s = "leetcode"

**Output:** "leotcede"

**Constraints:**

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

# Approaches
## Collect Vowels and Rebuild
This approach involves two separate passes over the string. The first pass collects all the vowels into a separate data structure. The second pass constructs a new string, replacing the original vowel positions with the collected vowels in reverse order.
**Time:** O(N), where N is the length of the string. We make two full passes over the string: one to collect vowels and another to build the result string. Each pass takes O(N) time. · **Space:** O(N). We use extra space for storing the vowels (O(K), where K is the number of vowels) and for the `StringBuilder` to construct the final string (O(N)). In the worst case, where all characters are vowels, this becomes O(N).
**Pros:** Simple to understand and implement.; Clearly separates the concerns of finding vowels and reconstructing the string.
**Cons:** Less efficient due to two passes over the string.; Requires extra space proportional to the number of vowels and the length of the string.
### Explanation
The core idea is to first isolate the vowels from the string, reverse them, and then place them back into the positions where vowels originally appeared.

**Algorithm:**
1.  Create a list or a string to store all the vowels from the input string `s`.
2.  Iterate through `s` from beginning to end. If a character is a vowel, add it to our vowel collection.
3.  After the first pass, our collection contains all vowels in their original order (e.g., for 'IceCreAm', we get ['I', 'e', 'e', 'A']).
4.  Now, create a `StringBuilder` to build the final result.
5.  Initialize a pointer to the end of our vowel collection.
6.  Iterate through the original string `s` again. If the character at the current position is a vowel, append the vowel from our collection (using the pointer) to the `StringBuilder` and move the pointer backward. If it's a consonant, append the original character.
7.  Finally, convert the `StringBuilder` to a string.

**Code Snippet:**
```java
class Solution {
    public String reverseVowels(String s) {
        // Helper to check if a character is a vowel
        String vowels = "aeiouAEIOU";

        // 1. Collect all vowels from the string
        StringBuilder vowelCollector = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (vowels.indexOf(c) != -1) {
                vowelCollector.append(c);
            }
        }

        // 2. Reverse the collected vowels
        vowelCollector.reverse();

        // 3. Build the result string
        StringBuilder result = new StringBuilder();
        int vowelIndex = 0;
        for (char c : s.toCharArray()) {
            if (vowels.indexOf(c) != -1) {
                result.append(vowelCollector.charAt(vowelIndex));
                vowelIndex++;
            } else {
                result.append(c);
            }
        }

        return result.toString();
    }
}
```
### Algorithm
*   Create a helper data structure (like a `List` or `StringBuilder`) to store vowels.
*   Iterate through the input string `s` and add every vowel encountered to the helper structure.
*   Reverse the collection of vowels.
*   Create a `StringBuilder` for the result.
*   Iterate through the input string `s` again. For each character:
    *   If the character is a consonant, append it to the result.
    *   If the character is a vowel, append the next vowel from the reversed vowel collection to the result.
*   Return the final string from the `StringBuilder`.

## Two-Pointer Approach
A more efficient, in-place approach that uses two pointers to swap vowels. One pointer starts from the beginning of the string and another from the end. They move towards each other, swapping vowels as they find them.
**Time:** O(N), where N is the length of the string. The `left` and `right` pointers each traverse the array at most once, resulting in a single-pass algorithm. · **Space:** O(N). In Java, strings are immutable, so we must convert the string to a character array, which requires O(N) space. In languages with mutable strings, the space complexity would be O(1) (excluding the space for the vowel set, which is constant).
**Pros:** More efficient as it requires only a single pass over the data.; Considered an in-place algorithm conceptually, though Java's string immutability requires an auxiliary character array.; Lower constant factor for space usage compared to the two-pass approach.
**Cons:** The logic can be slightly more complex to write correctly compared to the two-pass approach.
### Explanation
This method avoids the need for extra storage for vowels by performing swaps directly on a character array representation of the string. It uses a single pass where two pointers converge.

**Algorithm:**
1.  Convert the input string `s` to a character array, `chars`, since strings are immutable in Java.
2.  Initialize a `left` pointer to `0` and a `right` pointer to `s.length() - 1`.
3.  Use a `while` loop to continue as long as `left < right`.
4.  Inside the loop, move the `left` pointer forward until it points to a vowel.
5.  Move the `right` pointer backward until it points to a vowel.
6.  If `left` is still less than `right`, it means we have found a pair of vowels. Swap the characters at `chars[left]` and `chars[right]`.
7.  After the swap, increment `left` and decrement `right` to continue the search for the next pair.
8.  Once the loop finishes (when `left >= right`), convert the modified character array back into a string and return it.

To efficiently check for vowels, a `Set` can be used for O(1) lookups.

**Code Snippet:**
```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public String reverseVowels(String s) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        char[] chars = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            // Find the first vowel from the left
            while (left < right && !vowels.contains(chars[left])) {
                left++;
            }

            // Find the first vowel from the right
            while (left < right && !vowels.contains(chars[right])) {
                right--;
            }

            // Swap the vowels
            if (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;

                // Move pointers inward
                left++;
                right--;
            }
        }

        return new String(chars);
    }
}
```
### Algorithm
*   Convert the input string `s` to a character array `chars`.
*   Initialize two pointers, `left = 0` and `right = s.length() - 1`.
*   Loop while `left < right`:
    *   Increment `left` until `chars[left]` is a vowel.
    *   Decrement `right` until `chars[right]` is a vowel.
    *   If `left < right`, swap `chars[left]` and `chars[right]`.
    *   Increment `left` and decrement `right`.
*   Convert the `chars` array back to a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String reverseVowels(String s) {
    boolean[] vowels = new boolean[128];
    for (char c : "aeiouAEIOU".toCharArray()) {
      vowels[c] = true;
    }
    char[] cs = s.toCharArray();
    int i = 0, j = cs.length - 1;
    while (i < j) {
      while (i < j && !vowels[cs[i]]) {
        ++i;
      }
      while (i < j && !vowels[cs[j]]) {
        --j;
      }
      if (i < j) {
        char t = cs[i];
        cs[i] = cs[j];
        cs[j] = t;
        ++i;
        --j;
      }
    }
    return String.valueOf(cs);
  }
}
```

### CPP

```cpp
class Solution {
public:
  string reverseVowels(string s) {
    bool vowels[128];
    memset(vowels, false, sizeof(vowels));
    for (char c : "aeiouAEIOU") {
      vowels[c] = true;
    }
    int i = 0, j = s.size() - 1;
    while (i < j) {
      while (i < j && !vowels[s[i]]) {
        ++i;
      }
      while (i < j && !vowels[s[j]]) {
        --j;
      }
      if (i < j) {
        swap(s[i++], s[j--]);
      }
    }
    return s;
  }
};

```

### Python

```python
class Solution:
    # class Solution : def reverseVowels ( self , s : str ) -> str : vowels = "aeiouAEIOU" # or, vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'} 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 )
    def reverseVowels(self, s: str) -> str: vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'} i, j = 0, len(s) - 1 chars = list(s) while i < j: if chars[i] not in vowels: i += 1 elif chars[j] not in vowels: j -= 1 else: chars[i], chars[j] = chars[j], chars[i] i += 1 j -= 1 return '' . join(chars)

```