"Rotating the string" optimization

Question

Below is the code for the problem at Codechef. I have made use of the String method .equals in my solution which is working fine for all the test inputs. However, I am getting a Time Limit Exceeded when I submit to the Judge. I need your ideas on optimizing the code.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main
{

    public static void main(String args[]) throws IOException
    {

        BufferedReader in =new BufferedReader(new InputStreamReader(System.in));

        int not=Integer.parseInt(in.readLine());

        for(int i=0;i<not;i++)
        {

            String s=in.readLine();
            int count=0;


            String inp[]=in.readLine().trim().split(" ");

            int m=Integer.parseInt(inp[0]);
            int p=Integer.parseInt(inp[1]);

            //System.out.println(m+" "+p);




            String temp=s;


            for(int b=0;b<(Integer.MAX_VALUE/2);b++)
            {

                //System.out.println(temp);
                String s1=rotate(m,temp);   
                //System.out.println(s1);
                count++;
                if(s1.equals(s))
                    break;


                String  s2=rotate(p,s1);
                //System.out.println(s2);
                count++;
                if(s2.equals(s))
                    break;

                temp=s2;



            }

            if(count>0)
                System.out.println(count);
            else
                System.out.println(-1);


        }

    }   private static String rotate(int m, String s) {

        char sa[]=s.toCharArray();

        int l=sa.length;



        StringBuilder sb=new StringBuilder();

        for(int j=m-1;j>=0;j--)
        {


            sb.append(sa[l-1-j]);





        }

        for(int k=0;k<(l-m);k++)
            sb.append(sa[k]);



        return sb.toString();
    }




}

Answer 1

I would use an entirely different strategy to determine the number of times needed to rotate the string: addition.

Since rotating a string by a and then b yields the same result as rotating it a+b, we do not need to keep track of the string at all, only the equivalent rotation. However, we do need to be able to detect if the string is actually just concantenations of some substring; in that case we can treat it as if its length were the length of the repeated substring.

Here are the steps I would use for each string:

1. Match the string against the regular expression (.+?)\1+. This uses a backreference to find the iterated portions of the string. (FYI, this regex may need some adjustment.)

   static final Pattern iteratedSubstring = Pattern.compile("(.+?)\\1+");
   static int reducedLength(String string){
       Matcher m = iteratedSubstring.matcher();
       if(m.matches(input)) return m.group(1).length()
   
       return string.length()
   }
   

2. Repeatedly accumulate the two rotations until the rotation is congruent to zero modulo the length.

   static int identityRotationCount(final int length, int ... rotations){
       rotations = Arrays.stream(rotations).parallel().flatMap(i->i%length).toArray();
   
       /* alternately, if you can't use java 8 you can do this, although it's slower:
       for(int idx = 0; idx < rotations.length; idx++)
           rotations[idx] %= length;
       */
   
       int count = 0, rotation = 0;
   
       while(true)
           for(int rot: rotations){
               count++;
               rotation += rot;
               if(rotation == length) return count;
               if(rotation > length) rotation -= length;
           }
   }
   

   There may be even faster methods to compute this, including variants on algorithms for finding a GCD or other discrete algebra type things.

3. At least at first, you should be using a Scanner to process the input, because inevitable parsing logic bugs from doing the parsing yourself will make debugging anything else extremely difficult.

   try(Scanner in = new Scanner(System.in), PrintWriter out = System.out){
       // ...
   }
   

4. Finish the program:

   in.nextInt(); //discard input entry count, don't need it.
   
   while(true){
       if(!in.hasNextLine()) break;
       String string = in.nextLine();
   
       if(!in.hasNextInt()) break;
       int monkey = in.nextInt();
   
       if(!in.hasNextInt()) break;
       int po = in.nextInt();
   
       out.println(identityRotationCount(reducedLength(string), monkey, po));
   }
   

5. If you do not want to use a Scanner, try something like this:

   try(BufferedReader in = new BufferedReader(System.in), PrintWriter out = System.out){
       int n = Integer.parseInt(in.readLine());
   
       for(int idx = 0; idx < n; idx++){
           String string = in.readLine();
   
           String [] rots = in.readLine().split("\\s");
   
           int monkey = Integer.parseInt(rots[0]),
                     po = Integer.parseInt(rots[1]);
   
           out.println(identityRotationCount(reducedLength(string), monkey, po));
       }
   }
   

Answer 2

First of all, clean up your code, it's a mess.

---

Java normally uses a modified K&R Style with the opening braces on the same line and omitting braces is not allowed, like this:

void test() {
    if (something) {
        // code
    } else {
        // code
    }
}

---

public static void main(String args[]) throws IOException
{

Your main method should not throw exceptions, ever. It should handle exceptions and fail gracefully if necessary.

---

BufferedReader in =new BufferedReader(new InputStreamReader(System.in));

int not=Integer.parseInt(in.readLine());

First rule of naming variables is: You name the variables after what they contain. not is a not very good name for a variable, neither is in or sa. Ideally you could read every line of the code without context and tell what it does.

Quick: Tell me what this code piece does: sb.append(sa[l-1-j]);