Getting TLE In just one case[LONGPALI]
Any ideas, what could be missing?
i am trying to loop as(for input “abcde”)
abcd bcde
abc bcd dce
ab bc cd de
a b c d e

see the test case bro

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

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 :slight_smile:

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.

Please could you provide a link to any of those solutions.

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.


(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