Chef, Chefina and Their Friendship

The below code is my approach to the problem. Can anyone explain me why it was showing TLE.

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while (t–>0) {
String str=sc.next();
System.out.println(isBreakable(str));
}
}

public static int isBreakable(String str){
int count=0;
int n=str.length();

  for(int i=0;i<n/2-1;i++){
  	String str1=str.substring(0,i+1);
  	String str2=str.substring(i+1,i+2+i);
  	if(!str1.equalsIgnoreCase(str2))
  		continue;
  	String str3=str.substring(i+i+2,n);
  	int m=str3.length();
  	if(m%2!=0){
  		continue;
  	}
  	String str4=str3.substring(0,m/2);
  	String str5=str3.substring(m/2,m);
  	if(str1.equalsIgnoreCase(str2) && str4.equalsIgnoreCase(str5))
  		count++;
  }

  return count;

}
}

I have the same problem

1 Like

No issues, just trying if anyone able to help me to find out the mistake is my code or suggest me better approach.

@anubhavs your code and approch seems right but solution time complexity is O(N^2) which is not intended. See the editorial, it explains some of the methods to solve it efficiently.

1 Like

@rishup_nitdgp

Please help why i am getting TLE problem

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef{

public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T-->0)
{	

	String s=sc.next();
	
	int n=s.length();
	int count=0;
	String s1="",s2="",s3="",s4="";
	
	for(int i=2;i<(n-2);i+=2)
	{
		s1=s.substring(0,i/2);
		s2=s.substring(i/2,i);
	//	System.out.println("ii:"+ii);
		if(s1.equals(s2))
		{
		s3=s.substring(i,i+ (n-i)/2);
		
		s4=s.substring(i+(n-i)/2,n);
		if(s3.equals(s4))
			count++;
		}
	}
	
	System.out.println(count);
}
}

}

@rishup_nitdgp
Please reply on this as Complexity in my code is O(N) then why am i getting TLE. issue i also have check answers of other people but same approach they took still
i am getting TLE

The method substring() has an O(n) time complexity. substring() is being used inside the for loop. This makes it O(n^2).

1 Like

Well test cases are still not updated .

but then O(n2) cases are showing TLE ,previously they were accepted,they have updated the cases