Longest palindromic substring — O(n^2) with dynamic programming

Problem: Given a string of characters, find the longest palindromic substring.

Video tutorial: https://www.youtube.com/watch?v=-3xrCmE0wUo

1 Like

Its a nice problem in Mixt-Dynamic-Programming :slight_smile:

2 Likes

And hashing can do it trivially in O(N * logN), so what’s the point here? If an O(N ^ 2) solution is allowed then literally anyone can come up with somethin’ like this.

Can be done in O(n) using manachers algorithm.

2 Likes

Be honest here who remembers its implementation?

1 Like

i have watched videos on manachar’s algorithm but i couldn’t figure out how to code that algorithm, can you please help me by posting the code and help me understand it ?

https://cp-algorithms.com/string/manacher.html
This might help