Is there a way to reverse a string faster than O(n)?

I have the following code which takes more than 5 seconds to run with the argument -Xmx<1024M>.

I am aware that the for loop takes O(q) time, as well as the reverse() and toString() take O(n) time each.

Is there a way to reverse the string in less than O(n) time? Or is something else slowing the code down? Any help would be welcome!

class Main {
  public static void main(String[] args){
    String s = "a";
    String qa = "200000";
    int q = Integer.parseInt(qa);
    String[] t = new String[q];
    for(int i = 0; i < q; i++) {
      if(i%2==0) {t[i] = "2 1 x";}
      if(i%2==1) {t[i] = "1";}
      if(t[i].toCharArray()[0] == '1') {
        StringBuilder rev = new StringBuilder(s).reverse();
        s = rev.toString();
      } else {
        char letter = t[i].toCharArray()[4];
        if(t[i].toCharArray()[2] == '1') {
          s = letter + s;
        } else {
          s = s + letter;
        }
      }
    }
    System.out.println(s);
  }
}

Regardless of what is it supposed to do (I have no idea), I found the following problems:

• Multiple instantinations of StringBuilder in each iteration.
• String concatenation using + operator.
• Repetitive usage of Sring::toCharArray (see the 2nd solution)

You will achieve a faster result using directly only one instance of StringBuilder:

String s = "a";
String qa = "200000";
int q = Integer.parseInt(qa);
String[] t = new String[q];
StringBuilder sb = new StringBuilder(s);       // Instantiate before the loop
for (int i = 0; i < q; i++) {
	if(i%2==0) {t[i] = "2 1 x";}
	if(i%2==1) {t[i] = "1";}
	if(t[i].toCharArray()[0] == '1') {
		sb.reverse();                          // all you did here is just reversing 's'
	} else {
		char letter = t[i].toCharArray()[4];
		if(t[i].toCharArray()[2] == '1') {
			sb.insert(0, letter);              // prepend a letter
		} else {
			sb.append(letter);                 // append a letter
		}
	}
}

Another thing is that you multiple times define a String such as t[i] = "2 1 x"; and then you compare with t[i].toCharArray()[0]. Pre-definig these immutable values and using char[][] should help too:

String s = "a";
String qa = "200000";
int q = Integer.parseInt(qa);
char[][] t = new char[q][];                    // char[][] instead of String[]
char[] char21x = new char[]{'2', '1', 'x'};    // predefined array
char[] char1 = new char[]{'1'};                // another predefined array
StringBuilder sb = new StringBuilder(s);       // Instantiate before the loop
for (int i = 0; i < q; i++) {
	if(i%2==0) {t[i] = char21x;}     // first reuse
	if(i%2==1) {t[i] = char1;}       // second reuse
	if(t[i][0] == '1') {             // instead of String::toCharArray, mind the indices
		sb.reverse();                // all you did here is just reversing 's'
	} else {
		char letter = t[i][2];       // instead of String::toCharArray, mind the indices
		if(t[i][1] == '1') {
			sb.insert(0, letter);    // prepend a letter
		} else {
			sb.append(letter);       // append a letter
		}
	}
}

Edit: I have tested the solution with the simplest way possible using a difference of System.currentTimeMillis() on my laptop:

• Original solution: 7.658, 6.899 and 7.046 seconds
• 2nd solution: 3.288, 3.691 and 3.158 seconds
• 3rd solution: 2.717, 2.966 and 2.717 seconds

Conclusion: I see no way to improve the algorithm itself in terms of the computation complexity, however, using the correct ways to treat Strings helps to reduce the time complexity 2-3 times (in my case).

General advice: What you can instantiate and define before the loop, do it before the loop.

> Is there a way to reverse the string in less than O(n) time? Or is something else slowing the code down?

No there is no way to reverse a string in less than O(n) time: A program that produces an output of size n necessarily takes o(n) time at the minimum.

Your code has lots of unnecessary operations that slow the program down. The program produces 50000 letters x, followed by one letter a, followed by another 50000 letters x. Here is a much faster (and easier to understand) implementation of the same program.

class Faster {
    public static void main(String[] args) {

        String hundredXs = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";

        for (int i = 0; i < 500; i++)
            System.out.print(hundredXs);

        System.out.print("a");

        for (int i = 0; i < 500; i++)
            System.out.print(hundredXs);

        System.out.println();
    }
}