0
\$\begingroup\$

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

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$
  • 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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the advice @vnp. I had added .intValue() as a precautionary measure against the compiler. \$\endgroup\$ Jul 19, 2018 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.