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

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…

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

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.

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.

sorry, i found the mistake