# Reversing the vowels in a String

Given a string, reverse only the vowels present in it and print the resulting string.

Input:

First line of the input file contains an integer T denoting the number of test cases. Then T test cases follow. Each test case has a single line containing a string.

Output:

Corresponding to each test case, output the string with vowels reversed.

Example:

Input:

4

geeksforgeeks

practice

wannacry

ransomware

Output:

geeksforgeeks

prectica

wannacry

rensamwora

My approach:

/*package whatever //do not write package name here */

import java.util.Scanner;
import java.io.IOException;
import java.lang.StringBuffer;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class GFG {

private static String reverseVowels (String str) {

List <Character>vowels = new ArrayList <>();

List <Character>values = new ArrayList <>();
List <Integer>keys = new ArrayList <>();

for (int i = 0; i < str.length(); i++) {
if (vowels.contains(str.charAt(i))) {
}
}

StringBuffer sb = new StringBuffer(str);

Collections.reverse(values);
int count = 0;

for (Integer num : keys) {
sb.replace(num.intValue(),num.intValue() + 1,String.valueOf(values.get(count)));
count++;
}

return sb.toString();

}

public static void main (String[] args) throws IOException {
Scanner sc = new Scanner (System.in);
int numTests = sc.nextInt();

for (int i = 0; i < numTests; i++) {
String str = sc.next();
System.out.println(reverseVowels(str));
}
}
}


I have the following questions about my code:

1) How can I further improve my approach?

2) Is there a better way to solve this question?

3) Are there any grave code violations that I have committed?

4) Can space and time complexity be further improved?

My time complexity is O(n) and space complexity is also O(n) currently.

Reference

• Time complexity is $O(n)$ indeed. Since every input character must be inspected, this asymptotic is impossible to improve. However, it is possible to improve the constant. See below.
• Space complexity is $O(n)$ indeed. However, it is possible to solve the problem is $O(1)$. Consider two iterators, one running left to right, and another running right to left. As long as the first iterator points a consonant, print it. As soon as it hits a vowel, scan the second iterator (right to left) until it finds a vowel, and print that vowel. Notice that this approach also doesn't need values and keys - and hence doesn't need to build them. This is how time complexity is also improved.
sb.replace(num.intValue(),num.intValue() + 1,String.valueOf(values.get(count)));