Longest Common Subsequence (Dynamic Programming)

[@lordozb]

Simplest explaination I've ever seen of top-down approach. However, I wish the bottom-up method was explained more clearly.

[@LetsBeHuman]

kzbin.info/www/bejne/qYTRoGyoi52Fnsk

[@orangefield2308]

this is a great explanation, however, how would someone come up with this great algorithm on the spot during the interview? my friend failed an interview, because he didn't know the LCS equation, I guess we should just memorize interview questions at this point

[@qwarlockz8017]

@@orangefield2308 I do understand. I love being able to follow along and think.. WOW that is so clever! I like watching people fill up the DP matrix. But, I sort of feel the same about.. well.. do I have to memorize 10k equations? I dont know.. I do think we have to memorize the process and backing of a lot of these classics .

[@nikhilgumidelli6308]

For this who did not understand the bottom-up solution : The bottom up approach is similar to the recursive solution we start from n=0, m=0 . The first row and the first column will be 0. From n=1, m=1 we follow this : if P[n] == Q[m] : lcs[n,m] = 1 + lcs[n-1, m-1] else : lcs[n,m] = max(lcs[n-1, m] , lcs[n, m-1]) The thinking behind this is the same as the recursive solution but we are just starting from the first and does not involve multiple function calls on the stack. Hope this makes it clear.

[@coolchetang]

Thanks so much. Many people just start with a 2D array and some logic. You explained why we need that 2D array and clarified that it is intended for bottom up approach.

[@najimali32]

This is the best explanation of this problem I have seen. You explanation is great.

[@vladn.2332]

Very nice and clear explanation. After realizing how the recursive solutions works, I didn't have much difficulty to implement iterative version and then apply the same technique to find lcs of 3 strings. The logic for 3d array stays almost the same as for 2d array. Thank you, your video was very helpful!

[@manojg4451]

Oh,My god! Far better than my paid course explanation .Please do more problem solving videos

[@Gabriel-wq4ln]

Thank you for this excellent video. Straight to the point and really well explained.

[@SrinivasSakhamuri]

Python is so clean and easy on eyes for explaining algorithms. Great explanation and simple!

[@cloudfox1365]

CS Dojo, great video, I appreciate your work, your explanation actually helped break a mental block and see prefixes and suffixes.. in the bottom up approach, you might have explained a bit more why the value of matching characters in the P and Q strings is the value of the previous diagonal cell plus 1.. I think I now understand that, in the case of bottom up computation, we use suffixes (we look from current position to the end of the string) and if we match 2 characters than we take the result of the previously matched suffixes -- the result would be at location dp[i - 1][j - 1] and increment it by 1.. which is the previous diagonal cell.. Thanks

[@ajayshaan8573]

All this time I dreaded dynamic programming and thought it was some kind of arcane dark art. You made it very intuitive to understand! You. Are. Awesome! Keep the videos coming man!

[@bashmohandes]

Great video, one thing though, it is called Memoization as in (Memo) not Memorization as in Memory.

[@rajatchakraborty2058]

Here sir has said that we have to memorize the value in memory and the process of storing is called memoization

[@abdullahbukhari1469]

The best explanation ever thank you bro

[@dhruvgupta1993]

too simple explanation.....this recursive solution explained that formula which is used in DP approach. Thank you!!

[@jaswinderyadav2509]

Thanks dynamic programming was tough for me. I think now I understand it

[@tanayabiswas8781]

Very Good Explanation. Thank You

[@shree2710]

Omg you also have videos on dynamic programming!! Thank you so much!!

[@akshatbhutra7278]

VERY NICE CONCEPT ABOUT LONGEST COMMOM SUMSEQUENCE STRING

[@tonilipe]

this video was very helpful. thank you

[@anoopm3605]

Nice job explaining the concept.

[@The8merp]

Hi, this video was very informative, but it would be more helpful if you added links with the code for both the memoization and bottom up approach in the video description.

[@niranjanbs7549]

Great Dojo, base condition should be checking with -1!!

[@manaspatra2190]

This video was so helpful thank so much!!

[@Owenizedd]

Using your bottom-top solution and i use the P="AA" and Q="AAB" and the output is 2 (correct), i print the 2d array it looks exact same like what you drawn, but when i input P="BATD" and Q="ABACD". It print out 2, not 3.

[@venetacholakova9701]

Hi, I had the same issue. This was my mistake: * You need your 2D array to be with dimensions p.length()+1 and q.length()+1 So, when you call lcs the first time you pass p, q, 4 and 5 but you check p.charAt(4-1) and q.charAt(5-1) - like in the video (n-1 and m-1). Your final answer is in array[n][m] :) Lmk, if this helps

[@jugsma6676]

Can you try this? A = [] B = [] cache = [[0 for x in range(len(B))] for y in range(len(A))] def lcs(a, b, cache): for row in range(0, len(a)): for col in range(0, len(b)): if a[row] == b[col]: cache[row][col] = 1 + max(cache[row-1][col] , cache[row][col-1]) else: cache[row][col] = max(cache[row-1][col] , cache[row][col-1]) return cache[len(a)-1][len(b)-1]

[@MithleshKumar-iz1dz]

You are awesome dear. I really appreciate you. You are helping us. God bless you 😊

[@xiangwusong3984]

greate video about dynamic programming i have ever seen

[@amitvalse7802]

Well explained!! But I think the algorithm does not cover all the cases, for e.g. it would fail for P="AAAXAAA" and Q="AXA" try it from left or right. Will appreciate your response!

[@gagangowda9928]

Recursive solution works for this. Got 3.

[@jolystuff]

thanks, you actually make it easy to understand

[@nukkadcode8805]

Hi CSDojo, there is a typo mistake at time 7:51... Line 8th from top... i.e. Q(n-1) should be replace with Q(m-1).

[@weizhao900]

Same consider with you when I tested

[@FredoCorleone]

An idea would be to use an hash table with keys in form of (1e3 * N + M) as memoization mean. There only one thing that I don't get: why we don't memoize right after each recursive call?

[@manisirimalle5265]

which of these 3 approaches is best

[@MohamedSaad-er2pf]

Thanks for this great video 👍👍

[@enxingxiong7273]

Thank you! Your video helps me so much.

[@tcwang8697]

I especially like the part where you expend the possibility and then optimize the redundancy with DP. I used to watch another video, kzbin.info/www/bejne/eKrWf4uAfd92e9U, but I realize that jumping to the most optimal solution is not as helpful to fully understand the concepts and make them yours. Please keep bringing the contents like this. :)

[@Riteshbachhar]

CS Dojo didn't understand the bottom up approach. Would you like to help me out by sharing some resources or making a video?

[@jamesabasifreke]

Man, you are soooooo good! Please make more videos. I've subscribed.

[@annelivia4576]

Great explanation, Thank you!

[@tungthanhle6797]

It's a great video though, JK! can you please have a general method for DP problems? especially how to approach the problem and which ways can lead to the efficient solutions with several typical problems that have a high frequency in the top-tech interviews. Thanks, JK! PS: I like your explanation, so clear to me though!

[@techbenchers69]

Please make more videos on dynamic programming

[@keerthana02]

great job! love your videos ... looking forward for more

[@yiningli3160]

汝之秀，吾何时能及？when can I be as outstanding as you??? seriously, after I got a nice job offer(still a student now), I will share with you, thank you, i'm still waiting for a reply from a nice position, wish me good luck Sugishita san~

[@anbarasanv5625]

Hey Dojo. First of all thanks for great video, everything crystal clear except bottom up approach, could you help me with that ? I will really appreciate that. Thanks in advance.

[@shashanksharma21]

Another great video ! Thanks

[@neumoniad]

I feel like this video, while good intention, has a lot of explanations that don't necessarily make things clear. There are some leaps in the explanations that make it hard to follow along, as the reasoning for some of the actions taken while solving the problem.

[@ananthpadfoot]

The bottom up approach isn't clear. Can you explain in another video please?

[@sadsddaa4252]

very nice !thanks

[@farisEFFECT]

My brain hurts

[@LetsBeHuman]

kzbin.info/www/bejne/qYTRoGyoi52Fnsk

[@mattgreenrocks]

Great job on this, thank you.

[@zod1ack_csgo_clips425]

In the memoized solution, shouldn't the arr be arr[n+1][m+1] ?

[@abhis1560]

awesome explanation!!!

[@amrmoneer5881]

excuse me sir, u say that the worst case is 2^(n+m). On the diagram that u drew with n= 2 and m=3, the worst case would be 2^5 = 32. However, when i counted the states by hand they're only 19. please explain? 6:00.

[@scienceboom9971]

Loved it ! Thanks a ton!!

[@toekneemusic9732]

Can someone explain the bottom-up approach?

[@sprajapati2011]

kzbin.info/www/bejne/qYTRoGyoi52Fnsk&pbjreload=101

[@loltisharasha9753]

thank you soooooo much!! it is really helpful

[@Andrey-ny2dv]

Ideally, there should be reduction to using 2 arrays :)

[@kevintran6102]

Could you explain why LCS(P0, Q0) = max(LCS(P1, Q0), LCS(P0, Q1)) when last characters are different?

[@tinglinliu7476]

Yeah, I think this equation may not be right, hmm

[@tinglinliu7476]

For example, let's say P0 = "abc", Q0 = "cab", the LCS(P0, Q0) should be 3. While LCS(P1, Q0) = LCS("ab", "cab") = 2, and LCS(P0, Q1) = LCS("abc", "ca") = 2, so max(LCS(P1, Q0), LCS(P0, Q1)) will be 2 rather than 3. So I think the equation is wrong.

[@kevintran6102]

@@tinglinliu7476 In your example, LCS(P0, Q0) should be 2 which is "ab". The LCS should from left to right and could be noncontinuous.

[@tinglinliu7476]

@@kevintran6102 Oh, then that makes sense now. I thought it's find the longest common set of characters :)

[@kevintran6102]

Actually, I have tried to understand this logic and found out how it works. Suppose last character of P is P[i] and Q is Q[j] and P[i] != Q[j], so LCS never end at i and j together. It could be 2 cases: - LCS end at i - 1 and j if P[i - 1] == Q[j] - LCS end at i and j - 1 if P[i] == Q[j - 1]

[@angelapan66]

is this method the same as comparing whether the first character of P and first character of Q equal? if they match, recurse with the remaining string besides the first character?

[@chakradhar4378]

There is a mistake in code P[ n-1 ] != Q[ m -1]

[@mr.mystiks9968]

Bottom up approach was pretty bad. I can already see people filling in the table in any resource. But it seems like most people don’t understand the core thought process of filling that table. Fortunately I understood it after seeing this problem a few times.

[@RedPanther2030]

My first attempt to solve this with javascript (ps I didn't see the solution yet): function commonSequence(str1, str2) { var obj = {}; var string = ''; var arr1 = str1.split(''); var arr2 = str2.split(''); var shortLen = arr1.length < arr2.length ? arr1.length : arr2.length; var longLen = arr1.length > arr2.length ? arr1.length : arr2.length; //cache long string characters for(var j=0; j arr2.length ? arr1[j] : arr2[j]; obj[lChar] = 0; } for(var i=0; i

[@RedPanther2030]

PS: I'm using the shortest string to build the sequence. In this case "ABACD" is the shortest therefore the result would be ABCD

[@youssefzidan555]

Great job! Love your videos a lot! :)

[@JanacMeena]

Hi CS Dojo, it's incorrect to call it memorize, its memoized, without the letter R. It comes from the concept of writing something down on a memo pad.

[@sanjayd9675]

Can you explain it in detail sir It's hard for me

[@jeremyhon2775]

At 7:51, shouldn't the time complexity be 2^(max of n and m) instead of 2^(n + m) since technically the depth of the stack cannot go past the length of the strings. Anyone pls feel free to correct me if I am wrong

[@friohao5398]

When in the worst case ,the tree's height is n+m.Try to imagine like that, when start from root, when go to the tree's second level, one of n,m can minus 1, suppose it is m-1, and then go to the third level, it's n's turn to minus-1, and so on...So,the depth of the tree is n+m.

[@saminbinkarim6962]

We have to take the maximum value between A[n-1][m] and A[n][m-1] if the characters don't match?

[@sonofgod00]

thanks bro

[@tanishqjoshi2888]

Amazing!

[@ayushchauhan7227]

sir for me bottom-up method not clear

[@qwarlockz8017]

I am sure everyone knows this.. but memorize... actually is memoize

[@pedroamaya7539]

Is the running time for bottom up approach the same as Memoization?

[@MyMusics101]

Yes, it is. You are filling up a (n x m)-table, and for each cell, you only perform a constant-time operation on some adjacent squares you have previously filled in. Unfortunately, he only shows how to solve the example with the bottom-up approach rather than presenting a general algorithmic solution, but you can try to think through how each case is based on previous, already computed cases. As I said, his example hints at that.

[@irvinge4641]

why do we check the last characters? would it make sense to check the first characters are equal instead of the last one?

[@sanketsahu1745]

Yes, It would be the same thing. Just a small change : in the base case you need to use ( n == P.length() or m == Q.length() ) instead of sending n-1 you will send n+1 ..... similarly instead of m-1 send m+1

[@kevaljoshi4419]

This doesn't work apparently my m value I getting negative and there is an error list index out of range.

[@muhammadinaammunir6761]

What is the use of this?

[@_ityadi]

But how to find the long common subsequence. I mean the string. This algorithm is to find the max length.

[@chakradhar4378]

Just take a string and add the char to string everytime you increase result.. finally reverse the string

[@david_m157]

I get a syntactical error in Python on the first "else if" statement, no idea why.

[@sungchulyonseiackr]

else if ------> elif (in python)

[@sriharshacv7760]

I am finding it very difficult to visualize. Wish they stop asking these hyper abstract problems in interviews. I know of many people in my company who clear these problems but suck at real world problems. (very badly).

[@stewartzayat7526]

Can you do this iteratively?

[@chakradhar4378]

Yes we can do it iteratively but it takes O( n*m)

[@hharii]

Letting u know

[@adityarajiv6346]

Watch this video to learn how to solve variation of lcs: kzbin.info/www/bejne/mYHYgqSEisxrn7M

[@MrGraham20]

I have a Java implementation of the bottom-up solution here along with some details, if you want to see how it works: github.com/pekoto/PrincetonA/blob/master/PrincetonA/src/com/pekoto/algorithms/LongestCommonSubsequence.java

[@prat534]

Not sure why we are using recursion for this problem. Can't we simply do the below solution? def LCS(s1,s2): if len(s1) ==0 or len(s2)==0: return None res = "" for i in s1: if i in s2: res+=(i) s2 = s2.replace(i,"",1) return res # If you need length instead simply do len(res) print LCS('ABACD', 'BATD')

[@mohitkishore8494]

Your solution would return ABD which is not a subsequence. BAD is a subsequence. Your solution returns the common characters in the two strings.

[@LetsBeHuman]

Dude, what happend. 0:27 - You have underlined alphabets wrong.

[@ahmedmsabou4446]

THANK YOUU

[@jitkr1489]

brillant

[@watherby29]

ChatGPT solves problems involving LCS and others in 5-10 seconds for me. Programming is dying.

[@Jaxkr1]

This video has errors on bottom-up approach. Watch this instead: kzbin.info/www/bejne/qYTRoGyoi52Fnsk

[@jonnyd143]

Memoize, not memorize

[@matteolugli1607]

ngio' capito n cazz

[@danman6669]

It's "memoize," not "memorize."

[@sathishKumarElangovan]

great explanation!!

[@sanjayd9675]

Can you explain it in detail sir It's hard for me

[@sanjayd9675]

Can you explain it in detail sir It's hard for me