Scale Engineer

Reverse Vowels of a String

Easy
#0332Time: 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).5 companies
Patterns
Two Pointers
Data structures
String
Companies
AccentureAccoliteZohoTwitch

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

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();    }}

Complexity

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).

Trade-offs

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.

Solutions

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);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem