Krdytkyu

Inspired by CodeWars

We have a string s

Let's say you start with this: "String"

The first thing you do is reverse it: "gnirtS"

Then you will take the string from the 1st position and reverse it
again: "gStrin"

Then you will take the string from the 2nd position and reverse it
again: "gSnirt"

Then you will take the string from the 3rd position and reverse it
again: "gSntri"

Continue this pattern until you have done every single position, and
then you will return the string you have created. For this particular
string, you would return: "gSntir"

The Task:

In this kata, we also have a number x

take the above reversal function, and apply it to the string x times.

Return the result of the string after applying the reversal function to it x times.

Note:

String lengths may exceed 2 million and x may exceed a billion.
Be ready to optimize.

My solution works but times out and I am having trouble optimizing much further. The code contains a lot of useful comments but here is a summary of what I have attempted to do.

Cycle Length Calculation

Because the above algorithm generates cycles, we can calculate a strings cycle length and perform x % cycleLength to determine exactly how many iterations we must perform to get our end result, instead of having to calculate all the duplicate cycles. More on cycle lengths can be fouind here and here.

This method is better than nothing but can still get quite demanding on high cycle lengths. Potentially there is a better way of calculating the cycle length without so many iterations?

public final class XIterations {

    public static String xReverse(String s, long x) {

        // Using the cycle length and modular arithmetic,

        // We can find the exact number of reverse operations we will need to perform.

        // This way we will only perform operations we need to complete.

        long iterationsRequired = x % calculateCycleLength(s.length());



        // TODO: There may exist an algorithm that allows a linear transformation given x

        while (iterationsRequired > 0) {

            s = reverse(s);

            iterationsRequired--;

        }



        return s;

    }



    // The xReverse algorithm produces cycles and therefore duplicates.

    // This helper method determines the length of the cycle using the number of characters a string contains.

    // More detail on the algorithm can be found at:

    // https://oeis.org/A003558

    // https://oeis.org/A216066

    // TODO: There may exist an algorithm that requires less iterations to find the cycle length

    private static int calculateCycleLength(int n) {

        // Cache these so we only calculate them once.

        final int a = 2 * n + 1;

        final int b = 2 * n;



        int cycleLength = 1;

        while (true) {

            double c = Math.pow(2, cycleLength);

            if (c % a == 1 || c % a == b) {

                return cycleLength;

            }

            cycleLength++;

        }

    }



    public static String reverse(String s) {

        StringBuilder sb = new StringBuilder();

        int front = 0;

        int back = s.length() - 1;

        // Does not account for odd length strings. Will not add the middle character.

        while (front < back) {

            sb.append(s.charAt(back--));

            sb.append(s.charAt(front++));

        }



        // Account for odd length strings. Add the middle character that was never added by loop.

        if (front == back) {

            sb.append(s.charAt(front));

        }

        return sb.toString();

    }

}

I am mostly interested in optimization tips but of course any feedback is welcome.