# Getting TLE In just one case[LONGPALI]

https://www.codechef.com/viewsolution/32336991
Any ideas, what could be missing?
i am trying to loop as(for input “abcde”)
abcde
abcd bcde
abc bcd dce
ab bc cd de
a b c d e

see the test case bro
5000
abcdefghijklmnopqrstuvwxyz…

Can you please suggest what should i change(like faster methods). I m newbie in c++.
I think my solution to this problem is optimal( because it directly jumps into searching the maximum length palindrome string).
Is there a more optimized solution?

Please let me know of I am wrong somewhere…

its here by using Dynamic programming
@hackxsaras

1 Like

Though this would work for the given constraints, it wouldn’t if N≤10^5 or something like that.

I’d suggest to take a look at Manacher’s Algorithm. The complexity of the DP approach is O(N^2) where Manancher’s algo takes O(N).

But the DP approach would be easier if you’re new to CP

1 Like

but i saw some codes which were running in N^3 but were giving right answer actually the time limit here is 2secs.

Though other solutions are provided here are good enough but I would like if you would try and rethink your solution a bit which could change the complexity from `O(N^3)` to `O(N^2)`.
Instead of making all possible substrings you can iterate over each character of the string and try to extend on both sides till it is a palindrome.
eg:- `accdgbacabgc`
when you reach the character `c` on 8th position you would extend on both sides till it is a palindrome and update the max size when you reach the maximum length palindrome or the end of the string on either side.

2 Likes

Finally…
https://www.codechef.com/viewsolution/32412517
(that runs in best time xD)

1 Like

Yes! The solution is indeed `O(N^3)` but is well optimized and all thanks to the weak test cases which it just managed to pass in under the time limit.
I ran a custom test case and that took more than 2 sec.

1 Like

sorry, i found the mistake

1 Like