Longest Palindromic Subsequence

Given a string, find longest palindromic subsequence in this string.

[akhilguptavibrantjava]

Best videos ever on Dynamic Programming

[surajpant]

This man should be in Matrix movie... because he solves all DP problem using matrix😂 take it as compliment bro... thank you so much for easy explanation 👍👍

[sonali]

Thanks Tushar.. Your videos helped me land a job in Amazon six years back. You are a very good teacher. :)
Also, it will be good if you can explain top down approach at the end or the beginning. :)

[ShivangiSingh-wcgk]

Can you explain how you think about such stuff. I understand how things are working but I find it hard to make up the thing myself.

[fk]

Very very nicely explained. Could you also explain a bit about the Time and Space Complexity of this algorithm.

[amirkeibi]

Thanks. A colleague recently send me a link to this video and asked me a couple of questions about it and DP in general. I think it would've helped if it was explained for example why you're looking at the max of 2 numbers to determine the 3rd one (the recursive nature of DP). It's only clear to someone who has solved DP problems.

[NareshKumar-dwxp]

I have learned whole DP from you. Trust me, this guy taught everything by just matrix.

[thePrinceOfPurpose]

Here is my solution:


var s = "ABBBCCCDDDAE";



var out = findLongestString(s);



console.log(out);



function findLongestString(str){

var lookup = {};

var max = 0;

var start = 0;



if(str.length == 0){

return 0;

}



if(str.length == 1){

return 1;

}



for(i = 0; i < str.length; i++){

console.log(lookup);

var c = s[i];



if(lookup[c] && lookup[c] >= start){

start = lookup[c] + 1;

}

lookup[c] = i;



max = Math.max(max, i - start + 1);

}



return max;

}


Javascript style ;). Thank you for the helpful video.

[harshtekriwal]

Better solution is, Revese the string and apply longest common subsequence between the original one and the reversed one.

[madnorbi]

Kudos to your efforts. Keep up.

Ideas to some nice followups:
 running time, memory consumption (also considering trade-offs, we can answer just  the length with O(N) memory)
 actual code
 why does this specific recursion formula work (why don't we loose by choosing greedily the matching pair)

[meghu]

Thank you soo much....!!! U made Dynamic Programming easy!!!
Further we would expect the same for NP-Completeness problem. It is very hard to understand NPC problems and to solve them

[notreadyforanything]

Thanks for videos such as this. It helps a lot for self-learning.

Clear explanation. Thanks for the sharing!

[KansasFashion]

You are so good man, Thank you so much for teaching us that!

[qiaogao]

Thanks for sharing this solution. It's quite clear!

[tanzzzzz]

ah, this one is tough compared to the other videos i hv seen so far

[sahi]

Thanks a lot Tushar. Wonderful video. Helped a lot!!

[张莹-fv]

Thank you, your explanation is very clear

[KamilAliAgrawala]

Great video Tushar. Just a tip Label the matrix axis. I did my i, j the other way around and it tripped me up for a long time. Thanks

[shivaamidala]

querying the longest palidromic sequence is not clear. you explained which to pick not how are they picked