# “Rotating the string” optimization

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;

public class Main
{

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

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

int count=0;

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();
}

}

• The first step to clean code is proper formatting and avoiding pointless empty lines. Please fix your code, it will make it easier to read and review. – Ingo Bürk Apr 27 '14 at 14:58

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));
}
}


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));


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]);
• I would argue that a variable name like in could be very descriptive, depending on how you are using it. If you are declaring it in a try resource block, then it is extremely descriptive. – AJMansfield Apr 28 '14 at 21:21