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

editorial
, ,
1

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

Video tutorial: AMAZON CODING INTERVIEW - LONGEST PALINDROMIC SUBSTRING with Dynamic Programming (LeetCode) - YouTube

1 Like
2

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

2 Likes
3

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.

4

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

2 Likes
5

Be honest here who remembers its implementation?

1 Like
6

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 ?

8

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