Reversing the vowels in a String

Question

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

Answer 1

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