Any ideas, what could be missing?
i am trying to loop as(for input “abcde”)
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…
its here by using Dynamic programming
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
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.
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)
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