# How to avoid TLE in CHEFSHIP

To all those who are getting TLE in CHEFSHIP , your code is giving TLE on those strings in which all the characters are the same
There is some fixed answer for those special strings , try to figure it out ! 2 Likes

what is wrong in my code?

``````def ans(s,i,j,c=0):
N=len(s)
if 2*i>=len(s):
return c
elif (N-(2*i))%2!=0:
j=(N-2*(i+1))//2
return ans(s,i+1,j,c)
elif 2*i+j<len(s) and s[:int(i)]==s[int(i):int(2*i)] and s[2*i:2*i+j]==s[2*i+j:]:
c+=1
j=(N-2*(i+1))//2
return ans(s,i+1,j,c)
else:
return ans(s,i+1,(N-2*(i+1))//2,c)
def main(s):
d=Counter(s)
for i in d:
if d[i]%2!=0:
return 0
N=len(s)
if N-2>0:
return ans(s,1,(N-2)//2,0)
else:
return 0
t=int(input())
for _ in range(t):
s=str(input())
print(main(s))```

Or in which testcase it will fail?``````

one very smart observation is just find if all the character are same then return (1 + (n-4)/2)
And your code will get surely AC

1 Like

int n=s.length();
ll count=0;
for(int i=1;i<=(n/2)-1;++i)
{
if((s.substr(0,i)==s.substr(i,i)) && (s.substr(2*i,(n/2)-i)==s.substr((n/2)+i,(n/2)-i)))
{
count++;
}
}
cout<<count<<"\n";

try this.

What’s the reason behind this?

LOL you dont have to avoid TLE , testers themself avoided it

5 Likes

Here’s my solution using old school substr function. My AC submission

1 Like

This is ridiculous. My code is basically the same but I got a TLE thrice.

``````#include <bits/stdc++.h>

using namespace std;

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
int n = s.size();
int c = 0;
for (int i = 1; i < n/2; ++i)
{
c += (int)(s.substr(0, 2*i).substr(0, i) == s.substr(0, 2*i).substr(i, i) && s.substr(2*i, n-2*i).substr(0, (n-2*i)/2) == s.substr(2*i, n-2*i).substr((n-2*i)/2, (n-2*i)/2));
}
cout << c << '\n';
}
}
``````

i think i am doing the same thing but getting TLE
My Submission - https://www.codechef.com/viewsolution/33308621

I think this is bcoz there are many calls of substr here

But the complexity of `substr()` is O(n). And the sum of lengths in any iteration will be |s| and in this case, n = |s| .

1 Like