Longest Palindromic Subsequence Dynamic Programming

Coding Interview Question:-
Given a string S, Find the length of the longest palindromic subsequence.

Example:-
S = "LPASPAL"
length of the LPS = 5 ("LPSPL").

This video explains the Dynamic Programming approach to solve the Longest Palindromic Subsequence problem.

[mayanksharma]

Your video explains the concepts very easily, it can be more cooler If you code it in c/c++.

[DarkKnightUNS]

Awesome. I know your website from quora. Here is the best place to practice and understand more algorithm. Keep up your good work!

[jchakrab]

what are the 2 videos you mentioned in the beginning ? can u post the link

[pankajshet]

I agree with all the approaches you taught us here and am very thankful for the same.
But the problem we face is, we are not supposed to derive the solution we are just supposed to go and write the already known solution within 10-20 mins max. So it is not possible for us to draw the table or derieve the recurrence relation.
Considering the pressure at the interview, we have to bare, If possible can you find the more short cut approach to solve such long problems?

[gianlucavillani_]

how can i get the correct substring from the matrix? do you have an implementation in c?

[nandanyo]

Very clear explanation with visual aid, thanks so much for your time in making this video.

[apk]

Just wanted to drop a "thank you" to you guys ! You are doing such a great job . Your videos are making such a difficult problems look so easy . Kudos for all the good work !

[IDeserve]

Dear Friends,

If you like our content and would like us to continue making great content for you, please spread the word about IDeserve.
A share/appreciation from you on social network would mean the world to us!


Thanks,
-Team IDeserve.

[shivadamera]

nice explanation and i really appreciate your time.!!
As you asked to post interview questions, I m sharing one question.
By accepting n*n Matrix rotate the elements of the matrix (like concentric circles)
Thank you

[NaveenKumar-ndts]

Kudos for all the hard work!!

Btw I was wondering, how to handle if we were to print the longest palindromic subsequence ??
We can't build a pointer table like we did in LCS now can we?

Instead, I followed your first approach to find LCS between S and rev(S). But was just wondering what additions can be made to the algo presented in this video to do the same.

Cheers.

[riyadhhossain]

can you please explain the inner for loop please?

[suhasnayak]

Can we use an extra matrix as in case of longest common subsequence to get the longest subsequence ? Also how do we get all the subsequences ?

[AdiRenduchintala]

I think you can just use the longest common substring function, by using the string s and its reversed string s' as the 2 strings for LCS. Would this work?

[srinish]

Which two videos to be viewed before watching this video ??

[DivyaPaliwal]

Hi,
Can you please explain the problem through a video :
Count number of binary strings without consecutive 1’s
Thanks.

[divyadiv]

Great video ! The visualization helps me in understanding the concepts clearly.
I would like to know if you can come up with a way to retrieve the Longest Palindromic sequence.
For Example : if the input is AABCDEBAZ
The longest sequence would be : ABCBA, ABDBA, ABEBA

Can you retrieve all possible longest palindromic substring?

[knseeker]

you guys give amazing explanations, thank you very much

[MithleshKumar-izdz]

thanks, brother. So simple and clear explanation. Great!

[dzungdev]

Great job and clear explaination. Thank you!

[harishh]

great work, and your website looks awesome....thanks a lot .. you are genius..