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