Reverse Vowels of a String Leetcode Solution

Table of Contents

Problem Statement

In this problem a string is given and we have to reverse only the vowels of this string.

Example

"hello"

"holle"

Explanation:
before reversing : “hello”
after reversing : “holle”

"leetcode"

"leotcede"

Explanation:

Approach 1 (Using Stack)

We just have to reverse the vowels present in input string. So we can store all the vowels in a stack in the same order from left to right. Then again we can traverse the string and for each vowel character from left to right we will replace it with the topmost value of the stack.

Algorithm

Store all the vowel characters in a set.
Create a stack and push all vowel characters present in the input string from left to right.
Now again traverse the string for each character. If current character is vowel, replace it with the topmost character of the stack (rightmost vowel character of input string) and remove it from the stack.
Return the converted string.

Implementation for Reverse Vowels of a String Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

string reverseVowels(string s) {

    set<char> vowels={'a','e','i','o','u','A','E','I','O','U'};
    stack<char> stack;
    for(char c:s)
    {
        if(vowels.count(c)) stack.push(c);
    }

    for(char& c:s)
    {
        if(vowels.count(c)) 
        {
            c=stack.top();
            stack.pop();
        }
    }

    return s;
}

int main() 
{
    string s="leetcode";
    cout<< reverseVowels(s)<<endl;
   
   return 0; 
}

leotcede

Java Program

import java.util.*;

class Rextester
{ 
    public static String reverseVowels(String s) {

        char[] arr= s.toCharArray();

        Set<Character> vowels=new HashSet<Character>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');

        Stack<Character> stack=new Stack<Character>();

        for(char c:arr)
        {
            if(vowels.contains(c)) stack.push(c);
        }

        for(int i=0;i<arr.length;i++)
        {
            if(vowels.contains(arr[i])) 
            {
                arr[i]=stack.pop();
            }
        }

        return new String(arr);
    }
    
    public static void main(String args[])
    {
        String s="leetcode";
        System.out.println(reverseVowels(s));
        
    }
}

leotcede

Complexity Analysis for Reverse Vowels of a String Leetcode Solution

Time Complexity

O(N): We traversed the string only two times. Also push and pop operation on stack takes constant time and set of vowels has only 10 elements (i.e it will take constant time for finding a character), therefore time complexity is O(N).

Space Complexity

O(N): At worst stack can have all the characters of the input string. Hence space complexity is O(N).

Approach 2 (Single pass using two pointers)

We can also reverse the vowels in single pass using two pointers by following algorithm:

Create two variables start and end for pointing to vowels from left and right respectively.
Initialise as start=0 and end=length(string)-1.
Now run a loop while start<end.
Inside this loop run two loops for moving these two pointers start and end from left to right and right to left respectively so that they point to the next vowel.
Interchange the two vowel characters pointed by start and end.
Increase start and decrease end by 1.
Return the new string when start becomes greater the end.