Longest Palindromic Subsequence

[@akhilguptavibrantjava]

Best videos ever on Dynamic Programming

[@ShivangiSingh-wc3gk]

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.

[@YiboHuang]

Making up the thing is really hard, he probably didn't come up with it himself just saying.

[@rohitkumarkhatri2203]

No No, once ur level reaches at that point and u r in touch with these things for little longer, it starts happening that u can come up with solution. take very easier probs of DP. u will be able to make solution ur self, similarly solve most of them, move to hard DP prbs. after some solution u can solve ur self.. Tushar solved this himself or not, but he must be capable of making solutions himself.

[@unboxordinary]

if you guys don't know he worked at apple, aws, amazon www.linkedin.com/in/tushar-roy-4351091a/

[@nehaparmar497]

If you look up his solutions in GitHub, he has very clearly specified the links in the comments section at the top, to all the sites he referred.

[@sagardafle]

The answer lies at 0:55 : "How do we solve this ? Yes, we will use Dynamic Programming!"

[@sonali2090]

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. :)

[@amirkeibi2396]

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.

[@rheumaticharm9551]

Wow it's been 4 yrs but still I'll try to solve ur issue. The reason we are checking the max is because the matrix that we are building is designed in a way to give answers of subsequence of 1 lesser lenght in its adjacent spaces. And since WE NEED THE LONGEST PALINDROMIC SUBSEQUENCE HENCE we will consider the bigger one only. Although u can consider the other one and that will also lead u to some PALINDROMIC SUBSEQUENCE but it won't be the longest.

[@surajpant2150]

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 👍👍

[@NareshKumar-dw9xp]

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

[@cypherllc7297]

Are you able to do new DP questions after learning from here?

[@NareshKumar-dw9xp]

@@cypherllc7297 not completely but ys i have a good idea.

[@cypherllc7297]

@@NareshKumar-dw9xp should we memorize algorithm approach?

[@NareshKumar-dw9xp]

@@cypherllc7297 No , just do practice as much as you can . As you'll practice a lot , your mind will automatically prepared be when you will see new dp questions. But first, you need to train your mind.

[@blasttrash]

actually dont follow tushar approaches. They are bad. Who draws a dp table right away? you don't even know if its a dp problem first, you don't even know the dp formula first, you don't even know the return value first and so forth. Instead check aditya verma, andrey grehov, and mit videos for a better approach. Unless we come up with dp formula, dp questions are very hard. And for us to come up with dp formula in an interview you need to byheart a lot of patterns(a lot of people say its not needed, but this is exactly what they are doing unknowingly).

[@fk121276]

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

[@tapanchudasama6656]

The most important thing to code a DP problem is to understand why DP needs to be implemented in the first place. Then you need to come up with a recursive approach followed by a top-down memoization approach and then you know that okay, I can do this in the bottom-up approach too. Your videos can be a whole lot better if you could explain these concepts instead of straight away jumping to bottom-up DP. I'd recommend watching Aditya Verma's DP playlist for those who'd like to understand DP thoroughly. There are some 50 videos in that playlist. And's its pure gold.

[@2708meghu]

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

[@sahi145]

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

[@7810]

Clear explanation. Thanks for the sharing!

[@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)

[@harshtekriwal131]

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

[@abhishekjiwankar1]

there are scenario's where the reverse LCS method fails. This is better solution

[@SHUBHAMKUMAR-xh7dk]

@@abhishekjiwankar1 can you give a testcase for the same.

[@abhishekjiwankar1]

@@SHUBHAMKUMAR-xh7dk Sure.. here is one.. wcipeg.com/wiki/Longest_palindromic_subsequence#LCS-based_approach It gives wrong answer if there are multiple longest sub sequence

[@blasttrash]

@@abhishekjiwankar1 nice to know, but the article you mentioned only fails when asked to find the said LPS strings. If we only care about max length of palindrome subsequence, then I guess LCS and reverse approach works fine.

[@abhishekjiwankar1]

@@blasttrash that is correct

[@himanshuarora1907]

We could have taken the reverse and apply LCS to it. Is there anything wrong with that approach?

[@sehgaldam121]

+himanshu arora Yes you can do that and get the result in O(N^2)

[@shubhamraj7524]

epic man!! this actually works ...

[@shreejitnair2174]

The bottom up DP soluton also uses additional space right? I am not sure if any DP problem without memoizing and having additional memory to store past events, please correct me if m wrong.

[@ashwiniyengar8657]

I dont think that would work all the cases, here is an example where it wont work, 'aacdefcaa' -> here if we go by reverse and then LCS answer comes out to 3 i.e. aac or caa whereas the actual answer is 2 i.e. aa

[@tanzzzzz225]

@@ashwiniyengar8657 the answer would be 'aca', 'ada', 'aea', ... and so one but the longest is 3. So the answer is correct

[@shivaamidala]

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

[@TheElementFive]

“Here, they are same. Let’s see how it’s different.” I don’t know why but that cracked me up lol

[@rancui201]

your video never fails me down!!

[@utuk123]

Awesome Explanation.Thanks Tushar Sir.

[@张莹-f4v]

Thank you, your explanation is very clear

[@niharikapatil902]

Thanks for this amazing video!

[@qiaogao4251]

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

[@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.

[@notreadyforanything]

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

[@idiot7leon]

Thanks, Tushar. Super clear!

[@KansasFashion]

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

[@tanzzzzz225]

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

[@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

[@hirenpatel3462]

one other way to solve the above problem using reverse of string and Dynamic programming (LCS)

[@pastacork]

Tushar, thank you very much for your tutorials.

[@rsearchyt]

Very helpful. Thx for posting video Tusar.

[@devdev19]

Really great explanation

[@rajanrajendran9329]

You are another Sal Khan! Thanks Tushar!

[@ShankaranG]

very helpful. Thanks for posting the videos

[@rakeshroshan829]

Thanks Tushar , great explanation

[@czsokola]

One should mention the second possible base case. If your length is 2 and first letter is the same as the last (second) letter, then you get 2 + longestPalindrom(i+1; j-1) -> so you should define: When substring start is greater than its end, longest palindrom is 0. [This is the only possibility how to bring even numbers into result.]

[@MadHolms]

I finally understood it, thx!

[@shivamchauhan2673]

Bro, do please explain the logic behind what you are doing and also what the rows and columns signify in the matrix. Such ridiculous time waste. We are here to learn not, to just memorize the approach. Also the recursion formula is wrong: checkout for "bebeed" or simply take "aa" it will result in 3.

[@vishalmishra1937]

I guess correct part for if is Dp[I][j]=2+dp[i+1 ][j-1]

[@Relaxingmusic-tw4qn]

bhai adita verma bol ke ek channel hae wo approch sikhata hae, uska ye wala dekh sochna kaisae hae sikhaega banda kzbin.info/www/bejne/raaygIJ3id-Sf6M

[@HXYZZZ]

it is simply: row index represents start index of the string. column index represents end index of the string. when you are looking at full string ie., index 0 to 5, you are getting the result of previous comparison from index 1 to 4. if the value of this is 2 , then result will be 4 + current char match result for indexes 0 and 5. hope it helps.

[@aparnagopal5201]

LPS of a string is the same as the LCS between a string and it's reverse. Same time and space complexity

[@jb25379]

Yes, I prefer this approach as well. Fewer things to remember.

[@ManrajGrover]

Thank you so much for this wonderful explanation. :) Please continue to make such tutorials. Would appreciate follow up practice problems along with this.

[@ManrajGrover]

*****​​ No. I mean suggest some problems using this concept on Online Judges like SPOJ or CodeChef for practice. :) 

[@piyushjoshi5187]

Thankyou Tushar.... great... U R awesome...

[@bharath_v]

Tushar, You are amazing!👌

[@kishorebatta7395]

@Tushar - You are directly going to solving part. But please explain how does this problem satisfies dynamic programming properties. Without that it is highly difficult to solve other problems.

[@pagliacc1]

I have to mute or ff whenever you try to draw or erase something. The noise was just breathtaking.

[@mayankkumarthakur]

Great video as always. Tushar's videos really helped me to build my basic especially with dp and graphs. In the github code shared by him, he is filling every upper half cell in dp matrix. But, many times we may not need to fill all the cells. So, I think implementing it using recursion is a little faster for multiple testcases. Hope you have a good day.

[@malharjajoo7393]

The bottom up solution for this question will be 2 for loops but note that unlike the usual case , i will not start from 0 , instead from max value and towards 0

[@aviralverma1701]

Awesome tushar!

[@gdthegreat]

Nice videos sir. Why are you not active on KZbin since 2 years? Your content is great.

[@ameyapatil1139]

Brilliant explanation !

[@vatsayaynbinay160]

actually there is no need to add $ . This works just fine for even sized subsequence as well

[@code-at-amrita]

Nice video. Thanks for your clear explanation. God bless you Tushar.

[@saurabhsawant6487]

Nice Explanation ! very helpful. Thanks for uploading. If possible please upload some videos about how to approach such problems.(in short how to derive dp strategy )

[@lalitdudheria2580]

I had to login to thank you. Your videos are great :)

[@priyankpatel8034]

Great explanation 👍 thanks

[@anuragsandhu9590]

LANGUAGE USED IS JAVA class Solution {static int z1[]=new int[100]; static int z=0; static String q[]=new String [100]; public static void main(String[] args) { String ss="anuragnitinrotavatorsindhuracecar"; int n=ss.length(); char s[]=new char[100]; s=ss.toCharArray(); for (int i=0;i

[@lexicongem]

Awesome explanation!!!!

[@anuveshkothari]

understands the video but couldn't understand the implementation (your code in github) how are you calculating the dynamic array values

[@anuveshkothari]

two for loops that you are using

[@ShyamRonline]

anuvesh kothari Try this gist.github.com/bourneagain/fb7cc841112e24cce19c which is inline with the video explanation

[@bhavyasharma1064]

Thanks for these videos....very helpful....:)

[@user-zh6jt8tl9y]

This makes no sense. You don't explain why we're taking the max of the two substrings of the window.

[@Vidur11]

It makes sense. Suppose you have a substring "bdb". The total length of the palindromic subsequence(ps) bdb would be the cumulative sum of ps "bd"(1, since either b or either d alone) + length of ps "db"(1 since either b or d alone) + 2(to account for the two b's at the ends of the subsequence). In the case of bdb, we are taking the 2 b's and singular d which results in a length of 3.

[@Alwaysiamcaesar]

@@Vidur11 That doesn't make sense for input "agbdbaa". By that logic "agbdba" = 5, "gbdbaa" = 3, and "gbdba" = 3, so sum = 5 + 3 + 3 = 11 which is not the answer. The answer is supposed to be 5...

[@Vidur11]

@@Alwaysiamcaesar First of all, i mentioned that the total length of the ps is equal to the total length of it's subsequent "inner" palindromic subsequences. That means you have to look inside the string recursively. In your case of "agbdbaa", we know that "bdb" has a string length of 3. Taking L=6, we see that a and a are equal so we can add these two to the palindromic subsequence. Now contained within "aa" is the subsequence "bdb" of length 3. So the total length is 3 + 2 = 5 ("abdba"). I think you are making the mistake of taking the summation of all the substrings within the given substring, when in reality you must take only the summation of the valid palindromic subsequences within a substring.

[@shobhitsrivastava4496]

May god bless you, sir

[@KansasFashion]

Dude, I love you so much!

[@lac2275]

Well done bro!

[@HarishAmarnath]

no explaination on why we choose dynamic programming and no explaination of how to think about some question ... "yes we ll use dynamic programming " is all we got

[@rantlord8373]

Recursion with repeated data => use dynamic programming. Clear your concepts before attempting such problems.

[@babybear-hq9yd]

@Harish I posted an extended comment here recently explaining how to go about thinking up the solution, before diving into the DP code! Have a look :)

[@algoquest6741]

Is there a problem in the logic when two similar chars are present together? Consider this example input string: "AABCDB" I expect the output to be 4 (AABB) - but according to the logic presented here it says 3. Am I missing something?

[@ritwikdas9316]

+algoquest Dude AABB is not a palindrome

[@algoquest6741]

+Ritwik Das My bad. Apologize for missing that. Excellent videos +tusharroy2525

[@04pradeep]

Hi Tushar, its not clear in the video why you choose to create a matrix and fill it up in a certain way. When I trace it in paper it became clear for this problem,. For example in this video I was not able to understand why the values in the left of diagonal was left empty. I like your dynamic programming videos. I have written this comment in the interest of your videos becoming clearer and getting more views.

[@studyonline3236]

Hello Tushar , there's a case where the above code throws an error, when the length is 2 and the characters MATCH, we look diagonally downwards (According to that code), which would be empty . So when L==2 && inp(i)==inp(j) T[i][j]=2;

[@avleenmehal4648]

it will not be empty but with a value of zeross the whole matrix is filled with zeros unless changed

[@yanivgardi9028]

Thanks Tushar. can we generalize the solution by initializing the matrix in T[x][x-1] = -1 in that way, when dealing with length=1 we can follow the formula, without corner case for length 1. meaning: since string[start]==string[end] T[start][end] = 2 + max[T[start+1][end], T[start][end-1]) = 2+max(-1, -1) = 1

[@amadousallah6634]

Great explanation

[@rodrigoceccatodefreitas1656]

You are amazing man!

[@mouiadhani5167]

Thank you man...That was helpful!

[@MrThepratik]

very well explained.

[@ashwiniyengar8657]

Can you explain how this would work for a input string like this 'aacdefcaa' where the answer should be 2 'aa', but i am not getting the same result with this method?

[@alfonsocanady7564]

actually i think the answer should be aacdcaa since it's the longest non contiguous palindrone. It actually doesn't have to be aacdcaa it could be aacecaa or aacfcaa

[@nimishbajaj3815]

Thanks Tushar, if someone really wants to be very good in Programming which book/s do you recommend ?

[@osamaalkhodairy3155]

In my opinion begin with Competitive Programmer HandBook then CLRS ( *optional* ) then Competitive Programming 3 (CP3), hope it will help ^_^.

[@prashantpatel1314]

www.amazon.in/Algorithms-Unlocked-Thomas-H-Cormen/dp/0262518805/ref=as_li_ss_tl?ie=UTF8&linkCode=ll1&tag=freembastuff-21&linkId=e0c92577108ad9bec0651d4541572992

[@sonali9696]

Can't we do it like longest subsequence problem with first string as input A and second being reverse(A) - let's call it B. Here if A[i] == B[j] then dp[i][j] = dp[i-1][j-1] + 1. And if not equal then dp[i][j] = max(dp[i-1][j], dp[i][j-1]). I tried it with some examples and it works. I feel like you are essentially doing the same thing just in a more complicated manner. Please someone correct me if I am wrong in this method.

[@findingMyself.25yearsago]

Hi sonali, It won't work.... Try this example "aacabdkacaa" reverse would be "aacakdbacaa" Common subsequence would be aacakacaa But here the answer would be "aca"

[@winterheat]

how come bbbab is 4, for bbbb? Isn't bbabb ok too? So it is 5. Does it mean substring as in "you can delete any character"? Somewhat unclear

[@oxana602]

Tushar, thank you!!!

[@manavmohata1240]

You can just make a new string which is the reverse of the given string and find the longest common subsequence instead of this.

[@sumitchoube3875]

I also thought same approach

[@ujurak3899]

This may work for smaller test cases, but you will get TLE on longer strings with this approach.

[@nerocide1111]

I think an easier approach to this would be to use the OPT function

[@nerocide1111]

cool shades

[@junzhuang4923]

Thanks for your clear explanation on this table. Great.

[@xxxyyy8288]

look really happy this day

[@vipulsharma1897]

great work bro

[@edwinchen7729]

that was a quick and clear explanation, thanks a lot!!!

[@animatedzombie64]

here is the recurrent relation, so you can think of dp solution f(i, n) -> if Ci == Cn : 2 + f(i+1, n-1); 2 for two characters else: max( f(i+1, n), f(i, n-1) );

[@florakunjumon9180]

Thank you so much!

[@joeycopperson]

Nice explaination :)

[@MarcosCastroSouza]

thanks Tushar, well explained, have you participated in programming competitions?

[@devesh87]

can we extend this solution for longest palindromic substring?

[@aridokmecian]

Could we run Lowest Common Subsequence with original string and reverse of original string to receive the same answer?

[@GurudevKumar_NIT-A]

Yeah we can get correct result using this approach as well

[@ashwinap6995]

Hello +Tushar , How to find all possible palindromic subsequence in this string ?

[@piyushsrivastava9476]

excellent work.

[@zemalex89]

this is not working for: abcggfcab, by what you shown the number always will be odd

[@nafisfaiyaz7543]

It works. Maybe you made a mistake in implementation. Check it out: pastebin.com/s6Cpbv6g

[@expeng5861]

great video

[@akhilguptavibrantjava]

A small doubt :) While finding the characters that make the palindromic Sequence why do we go diaganally? I Guess Same result we can achieve if we go horizontally in backward direction and considering the character whenever the count becomes 2 less than the previous value.

[@rheumaticharm9551]

Becuase we are checking string according to lenght. For example at matrix[0][0] we are checking the string[0] which is char 'a'. Hence it is not possible to do horizontally if ur still using the same technique. Whole logic needs tk be changed in a totally different way.

[@minhluong4604]

How can i get the actual subsequence from this algorithm ?

[@halojustin01234567]

Do you initialize len 1, 2 and 3 entries first and then calculate others based on that

[@suyogkatekar8548]

This is pure gold

[@abhaydoke09]

Most of the time board is not visible. Good explanation!!

[@um4720]

Can you please share the code to print the LPS?

[@tushargupta2356]

should we first make the complete table before coding the problem in a competition?

[@dhriajbhandari]

According to this: en.wikipedia.org/wiki/Longest_palindromic_substring . The palindrome needs to a continous substring In the above example, g breaks the palindrome abdba. So the answer should be 'bdb'. Is that right?