trjhtr

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 <>();
 vowels.add('a');
 vowels.add('e');
 vowels.add('i');
 vowels.add('o');
 vowels.add('u');

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

 for (int i = 0; i < str.length(); i++) 
 if (vowels.contains(str.charAt(i))) 
 keys.add(i);
 values.add(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.



• 
  

  The line

  
  
  

  sb.replace(num.intValue(),num.intValue() + 1,String.valueOf(values.get(count)));
  

  
  
  

  is very hard to read. It is even harder to prove that it works correctly.