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 
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.
2 Likes
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