Longest Common Subsequence (2 Strings) - Dynamic Programming & Competing Subproblems

Рет қаралды 192,988

5 жыл бұрын

Code & Problem Statement @ backtobackswe.com/platform/content/longest-common-subsequence/video?
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: You are given 2 strings. Return the length of the longest subsequence that the 2 strings share.
Complexities
n = s1.length()
m = s2.length()
Time: O( nm )
We can upper bound time by the number of subproblems that we are going to solve.
Space: O( nm )
We upper bound space by the number of subproblems we will story answers to. Whether we do (n + 1)(m + 1) or (n)(m) doesn't matter asymptotically.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: kzfaq.info/love/Of7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: kzfaq.info
GeeksForGeeks: kzfaq.info/love/0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: kzfaq.info
Success In Tech: kzfaq.info/love/-vYrOAmtrx9sBzJAf3x_xw

Пікірлер: 1 035

@BackToBackSWE 5 жыл бұрын

Table of Contents: The Problem Introduction 0:00 - 0:25 What Is A Subsequence 0:25 - 1:00 Going Through Examples 1:00 - 2:37 Walking Through A Recursion Tree 2:37 - 12:00 Recursion Tree Finished: Our Answer 12:00 - 13:18 Dynamic Programming Table Walkthrough 13:18 - 13:43 What Are The Subproblems? 13:43 - 14:56 Defining Our Base Cases 14:56 - 16:24 Working On The Inner Table 16:24 - 22:49 DP Table Finished: Our Answer 22:49 - 23:27 This Is Not Intuitive At All 23:27 - 24:11 Time & Space Complexity 24:11 - 24:49 Subscribe Por Favor 24:49 - 25:11 The code for this problem is in the description. Fully commented for teaching purposes.

@panzhang9751 4 жыл бұрын

Like this time.

@BackToBackSWE 4 жыл бұрын

nice

@Repeatunt1l 4 жыл бұрын

Thank you for great explanation. Seems like the link to the code is missing in the description.

@AshishSingh-dn8wb 4 жыл бұрын

I cant find the code :/

@ankitsanghi 4 жыл бұрын

Where in the description is the code? I can't find it

@shubhamasati4488 5 жыл бұрын

somebody give this guy an oscar ...plz

@BackToBackSWE 5 жыл бұрын

haha

@arunsudharsan7437 4 жыл бұрын

please give him....

@BackToBackSWE 4 жыл бұрын

@@arunsudharsan7437 ye

@PiyushKumar-ey7qw 4 жыл бұрын

He surely deserves it. Till this date I was confused with the table thing, I mugged it up, but today I got it how each and every step is working.

@AnshumanKumar007 3 жыл бұрын

Wrong award. The Turing award perhaps.

@heyitsnikhil7956 4 жыл бұрын

"okay. this is not intuitive at all. I'm going to be outright and honest." -thanks for saying this. sounds relieving. 😂

@BackToBackSWE 4 жыл бұрын

it isn't lol

@heyitsnikhil7956 4 жыл бұрын

@@BackToBackSWE well, you made it really easy to understand. You are a great teacher! 🙌

@BackToBackSWE 4 жыл бұрын

@@heyitsnikhil7956 thanks

@adriantran6568 4 жыл бұрын

The dp table explanation is the most beautiful thing I've ever seen

@BackToBackSWE 4 жыл бұрын

nice

@muradquliyev6448 3 жыл бұрын

That is right

@ssparks1979 4 жыл бұрын

It was almost like you were speaking directly to me when you said "Stay with me! Stay with me! I know it is confusing." Thank you so much for this thorough explaination!

@BackToBackSWE 4 жыл бұрын

lmao - and sure

@sandarabian 4 жыл бұрын

I was so stumped when the problem was introduced, then at 4:22 it was like a bucket of genius water was dumped on my head. Genius!!

@BackToBackSWE 4 жыл бұрын

🚒🚒💧

@TeeheeTummytums503 5 жыл бұрын

This is absolutely unbelievable that I just now found your channel. Thank you so much for all your hard work. Keep up the great work!!!

@BackToBackSWE 5 жыл бұрын

Yeah, KZfaq probably won't pick up on this channel for another year or so but I'm ok with that. I'll keep going. And yeah, this video took 6 hours to produce. You guys keep me going. The problem isn't that I can't do these problems, it is that to EXPLAIN them WELL takes a lot of prep time. I have to code the solution, write teachers notes, shoot the video, edit the video, and publish. But yeah, thanks

@TeeheeTummytums503 5 жыл бұрын

@@BackToBackSWE have you considered mentioning your channel in the cscareerquestions subreddit? I know it would be incredibly beneficial to a lot of people there

@BackToBackSWE 5 жыл бұрын

@@TeeheeTummytums503 Tried. Talked to the mods. I tried everything. They won't budge so I gave up. It makes me really angry but at the same time, it is fine. I understand their position. I heard someone posted the channel once and it got like 50-60 upvotes and then the post got taken down. I think they just don't like promotions but...I just have to grow this so big that no one can ignore it. So that's what I'm trying to do. PS: I honestly don't think the channel is ready though. I have HUNDREDS of questions and tens of topics left to cover in high quality and that will take a long time.

@TeeheeTummytums503 5 жыл бұрын

@@BackToBackSWE big L for them. Thanks again for all you do.

@shanugarg8428 4 жыл бұрын

Hey guys here's another KZfaq channel for Algorithm : kzfaq.info/get/bejne/sNOmZ85n3bSqd58.html

@memoriesadrift 3 жыл бұрын

This is honestly the best video I have seen on dynamic programming on KZfaq. Mad respect to you for you for your down-to-earth, simple to understand explanations.

@ravishekranjan7282 4 жыл бұрын

This is the best explanation of LCS along DP available on internet.

@BackToBackSWE 4 жыл бұрын

thanks

@34521ful 5 жыл бұрын

This video was so good I almost cried... (tears of joy). Amazing work!

@BackToBackSWE 5 жыл бұрын

haha

@The8merp 4 жыл бұрын

Thank you so much. I have finally been able to understand Dynamic Programming Tabulation method. Most people when trying to explain it focus only on the table and don't explain how the code relates to the table properly. Now I understand it. You really have a gift for teaching, keep doing what you are doing. I will make sure to support this channel when I finally get a job

@BackToBackSWE 4 жыл бұрын

Nice, thx

@chiranjeevipippalla 3 жыл бұрын

I’m watching and practicing all your Dynamic programming, backtracking and recursion playlist and I can feel that I’m getting there (understanding, not memorizing). Thank you so much brother 👏👏👏🙏🏻🙏🏻🙏🏻

@AnnoyingBunny 2 жыл бұрын

Thank you for taking the time to make this video. I feel like I never fully understood dynamic programing. The way you break it down clicked instantly with me.

@doruwyl 4 жыл бұрын

What sets you apart from other coding solving videos is the depth you go into and the effort you put in order that your audience would really understand how to solve the problem. Well done!

@BackToBackSWE 4 жыл бұрын

ay, thanks

@tanvia29 5 жыл бұрын

I FINALLY understand. Thank you so much.

@BackToBackSWE 5 жыл бұрын

sure

@akashthakur05 3 жыл бұрын

Hi @Back To Back SWE I went through all the videos and was not even a single was as explanatory as you were. Thankyou man you made my day.

@bhaskarroy5435 5 жыл бұрын

I have gone through numerous videos but none of them could explain this problem in a level of depth like you did. Thanks a ton!

@BackToBackSWE 5 жыл бұрын

sweet thank you

@Riceballl88 4 жыл бұрын

This video is amazing -- can't believe how stumped I was at first until seeing you go through the table. Thanks so much for sharing.

@BackToBackSWE 4 жыл бұрын

thanks and sure.

@ShortGiant1 4 жыл бұрын

Thank you! You're like stackoverflow for leetcode. The place I look for help when I'm either stumped with a problem, or I've solved it but want the concept firmly set into my head.

@BackToBackSWE 4 жыл бұрын

great to hear.

@jameshizon4861 2 жыл бұрын

I like how when you explain, you keep us engaged. Keep up the enthusiasm!

@nhochamvui6070 2 жыл бұрын

holy moly this is what im looking for. many guys on youtube just showing me the trick to fill the table, they never explain how memoization-table working! Only you explain the key of the memoization approach!!!!!!!!!!!

@tpkkxbm 3 жыл бұрын

I never comment on KZfaq videos, but I have to for this incredible channel. The way you are helping me develop intuition for these algo problems is unbelievable. Thank you!

@BackToBackSWE 3 жыл бұрын

thanks!

@phanichoragudi57 5 жыл бұрын

Excellent explanation!

@BackToBackSWE 5 жыл бұрын

thanks, someone asked for this one so I did it (was going to happen this month anyway)

@Ashmole3 2 жыл бұрын

You are single handedly saving my algorithms class grade. You explain things in a way that I understand a lot better.

@JeannieTrinh 5 жыл бұрын

Omg this is the best video that's broken down this type of problem I've ever seen! You've explained this so perfectly and having the first portion connect with the DP table in the second part felt like magic to me XD. This video (plus many of your others) will be watched for yearssss.

@BackToBackSWE 5 жыл бұрын

thanks haha

@wadichemkhi 4 жыл бұрын

You sir deserve a medal ! You are making all stuff i was putting a lot of effort into learning very easy to understand. Thank you

@BackToBackSWE 4 жыл бұрын

thanks

@InfinityFnatic 5 жыл бұрын

The sheer energy and dedication of this guy is amazing, also outstanding explanation ability. If I had only had him as a teacher in high school man, I would have aced every single competition.

@BackToBackSWE 5 жыл бұрын

thanks....oh...and..................hey.

@rajeshseptember09 2 жыл бұрын

I was almost about to give up on "Dynamic Programming" until I saw this video. Best video on the internet for DP ! Hats off man !! Commendable job

@BackToBackSWE 2 жыл бұрын

Amaze! keep hustling buddy. Try our 5 day free mini course - backtobackswe.com/

@martinf490 5 жыл бұрын

This is the most intuitive explanation I've come across for this problem please don't stop.

@BackToBackSWE 5 жыл бұрын

the boat is moving full speed ahead

@mikasaackerman2694 3 жыл бұрын

OMG thank you!!! For the first time I feel like I've actually understood how DP works!

@BackToBackSWE 3 жыл бұрын

No problem!

@dineshsood9110 5 жыл бұрын

Finally, I could understand it. Thanks a lot for this awesome explanation. No one can explain it better.

@BackToBackSWE 5 жыл бұрын

thanks

@dahuskey81 2 жыл бұрын

Hell yeah!! Dude you rocked it. Thank you so much!! I love how you broke it down to the basic bottom up analysis!! Can't thank you enough!!

@yangyu4489 4 жыл бұрын

DUDE so thorough, entertaining, energetic. YUS. Need more of these videos man thank you so much for the work you do. I get DP now thanks to you!

@BackToBackSWE 4 жыл бұрын

nice. yus.

@akashsingha2616 5 жыл бұрын

Thank you for all your hard work to make us understand DP better.

@BackToBackSWE 5 жыл бұрын

sure

@saransh9306 5 жыл бұрын

Thank you sooooo much for all your hard work..This is an incredible content.

@BackToBackSWE 5 жыл бұрын

sure, enjoy

@SteversIO Жыл бұрын

The way you break this down is the most comprehensive and easy to understand of any videos I've watched 🙌🙏. Thank you for your content sir

@ale9507 2 жыл бұрын

Once again, a superb explanation. Showing the relation of the dp table to the recursion solution was an eye-opener. Now I fully understand what's going on, which really seems to be the vital part of understanding these dp problems. Thanks very much.

@rahulgarai4822 4 жыл бұрын

U have definitely given a good explanation of this. I want this types more. Thanks a lot👍

@BackToBackSWE 4 жыл бұрын

sure

@smithcodes1243 2 жыл бұрын

This guy is so good at explaining things! Keep it up, man!

@imnoodlehaus 2 жыл бұрын

Love your channel, how you are focused on setting one up to understand the problems and how to approach them.

@aakashbansal6627 4 жыл бұрын

Man, Can DP be explained any better than this? Hats off!!!! Thanks for all this stuff. Really made DP a cake walk for all us viewers...

@BackToBackSWE 4 жыл бұрын

nice

@lawlietnao_music 4 жыл бұрын

Dude this is the most amazing well-done explanation of DP that I've ever seen. I love u bro (big hug

@BackToBackSWE 4 жыл бұрын

hey

@MoonStruckHorrorsX 5 жыл бұрын

Amazing man. Simply amazing, your method of explaining is so simple and precise. Love the fact that you don't just jump into the code and tell "Oh it'll work like this".

@BackToBackSWE 5 жыл бұрын

sure, you're welcome

@satyagopalkothuru7745 3 жыл бұрын

The explanation is very clear and easily understandable. After listening to this video, I tried to code myself without seeing your code and finally I am succeeded in writing the code for this problem. Even my code looks different to your's but it worked. I really felt happy for that.

@tibinyte8697 3 жыл бұрын

You could use frequence vectors and do it in o(strlen(a) + strlen(b) + 26) time complexity and o(strlen(a) + o(strlen(b)) space complexity . It is easier more efficient and does not require DP.

@BackToBackSWE 3 жыл бұрын

@harshjoshi6257 4 жыл бұрын

i was gonna write that youre genius and the channel is underrated but then i saw that you have like a million subscribers(laughter emoji ) :)

@BackToBackSWE 4 жыл бұрын

thanks and we didnt have many subs for a while - this is the first comment I've read saying we have a lot of subs. This is like a pivotal point in external perception for the common watcher. Fascinating how things grow isn't it

@blackkiritok 3 жыл бұрын

Ok. How easily you explained this is beyond words. Many can code stuff but very VERY rare can explain the way you did. This problem haunted me for around 6 months and after this video I solved it without a sweat I can officially say you have GODLY skills. Thank you so much! I am going to spread this video (or your channel in general) to as many of my friends as possible. Please keep up the good work.

@BackToBackSWE 3 жыл бұрын

ok thx

@swapnilsengupta2217 4 жыл бұрын

It's amazing how lucidly he explains the problem. Keep going, sir, you rock!

@BackToBackSWE 4 жыл бұрын

ok thx

@sxganapa1974 5 жыл бұрын

Really good job

@BackToBackSWE 5 жыл бұрын

hey

@kanikaaapan9996 3 жыл бұрын

WOWW!! You explained soo well. I wish you would my college professor .How can there be 19 dislikes????

@BackToBackSWE 3 жыл бұрын

lol ye

@MahmoudMahfouz0 3 жыл бұрын

Those are probably collage "professors"

@samyakjain6855 4 жыл бұрын

You are absolutely nailing explaining hard concepts that are not at all intuitive in such a simple and easy to understand manner! Keep up the good work!

@BackToBackSWE 4 жыл бұрын

thx

@daleprather3026 3 жыл бұрын

This guy is the best there is. Thank you so much for your content.

@vedantiyangar151 4 жыл бұрын

Hey Ben! Thanks for this! Could we extend this to actually find the Longest common Subsequence instead of just the length? Or would that be more of a backtracking thing?

@BackToBackSWE 4 жыл бұрын

Yes, we can read the dp table using the same logic we used to construct it to trace back the original solution.

@AshishShukla-ro8oy 4 жыл бұрын

"JUST EXCELLENT!!!!!!"

@BackToBackSWE 4 жыл бұрын

@neozoan 3 жыл бұрын

Excellent! Excellent! Dynamic programming is my weakness, but little by little I'm getting my head around it. This video was super helpful in my quest.

@MicahBales 3 жыл бұрын

This video is fantastic. The teacher assumes we know nothing and walks us through every step in plain language. Bravo!

@arnobchowdhury3191 4 жыл бұрын

Hey, what's your plan for this Valentine's day? Benyam: To upload one of the most non-intuitve Dynamic Programming algorithm...

@BackToBackSWE 4 жыл бұрын

lol - was this video then

@dylanlarrabee2322 5 жыл бұрын

DO YOU S E E ? great video!

@BackToBackSWE 5 жыл бұрын

hahahahahahaha, yes I have odd mannerisms. I cannot overcome them.

@caaaarrllooooss 3 жыл бұрын

You're the GOAT at explaining these algorithms and problems. Thank you very much

@BackToBackSWE 3 жыл бұрын

@kuchuksary 2 жыл бұрын

THE BEST EXPLANATION EVER!!! Thank you!!!

@gunhopark9435 4 жыл бұрын

"So what happens is, this is what happens, do you see what happend?

@BackToBackSWE 4 жыл бұрын

haha what

@ErikaAlejandraGonzalez 3 жыл бұрын

why can't my algorithms analysis class be like this? would you mind teaching at my university? ahaha

@ErikaAlejandraGonzalez 3 жыл бұрын

our teacher treats us like idiots, and I'm like hellooo you just don't do your job right!!

@BackToBackSWE 3 жыл бұрын

yeah some suck

@javi3266 2 жыл бұрын

Dude you are AMAZING! Been trying to understand DP for a few days and I undertood it for once! Now I'm gonna keep watching your videos to see how to approach the other kind of problems. Keep up the good work!

@BackToBackSWE 2 жыл бұрын

Thanks! try out our 5 day free mini course backtobackswe.com/

@prathamj2215 4 жыл бұрын

YOU'VE EXPLAINED IT IN THE MOST BEAUTIFUL WAY POSSIBLE! I LITERALLY WATCHED 7 VIDEOS BEFORE THIS ONE AND YOUR'S TRULY EXPLAINED THE PROBLEM IN THE MOST UNDERSTANDABLE WAY!! THANK YOU! KEEP UP THE GOOD STUFF!!

@BackToBackSWE 4 жыл бұрын

OK I WILL CAN I TURN CAPS OFF NOW

@prathamj2215 4 жыл бұрын

@@BackToBackSWE XD

@user-lu4uo1wj5o 4 жыл бұрын

WHY CANT MY PROFESSOR EXPLAIN LIKE THIS? Thanks!

@BackToBackSWE 4 жыл бұрын

@CraigMine 4 жыл бұрын

Do you have to come up with something like that in an interview by yourself?

@BackToBackSWE 4 жыл бұрын

probably not

@sumansanyal2960 2 жыл бұрын

This is the only place where I found why the dp table contains n + 1 (+1 for empty strings) and how it corresponds to the intuitive recursion. Amazing stuff! Thanks a ton!

@mevalan1085 2 жыл бұрын

wow! Really great content! Love the dedication to explain it as clear as possible!

@Rock28099 5 жыл бұрын

0 dislike😎

@BackToBackSWE 5 жыл бұрын

@rajaganji7982 2 жыл бұрын

I think you made it harder than it already is. Why can't you just say your matching every char in one string to other in the matrix.and when at every point you will know how many have already matched and increase the count from their on.

@yanksrock1000 5 жыл бұрын

Wow, this is probably one of the best algorithm videos I've seen on KZfaq. Thanks!

@BackToBackSWE 5 жыл бұрын

sure

@Lynxdom 3 жыл бұрын

That is the greatest explanation for dynamic programming I've ever seen! Thank you!

@tomtomsg3908 2 жыл бұрын

Fricking amazing lecture dude! I have been reading all other articles, Wikipedia and other youtube videos! That dynamic table was always too crazy to look at! Your explanation is the best to make this problem looks like a easy 2D table problem! Awesome!

@vikranttyagiRN 4 жыл бұрын

You are an absolute legend. My teacher just did it without explaining anything. You nailed it. Thanks so much

@BackToBackSWE 4 жыл бұрын

thx

@shrsn 3 жыл бұрын

I always had troubles understanding how to approach the question in general. This is great. Helps understand why we are doing whatever we are doing . Best video

@BackToBackSWE 3 жыл бұрын

great!

@sureshgarine 2 жыл бұрын

OMG, you are the best at explaining this DP problem. This is by far the best explanation for LCS using DP

@hagrideli 2 жыл бұрын

The best explanation so far! Thanks man!

@parthokr 4 жыл бұрын

This video deserves more views! Hats off! You nailed it!

@BackToBackSWE 4 жыл бұрын

thanks

@faaizmasood9338 3 жыл бұрын

This is the perfect explaination! good work!

@thorthegreat10 4 жыл бұрын

Thank you man, one more well-known problem that became clear only after your explanation. Appreciate time and efforts!

@BackToBackSWE 4 жыл бұрын

great

@nidhigoswami2526 4 жыл бұрын

Your videos really help a lot... I was struggling a lot with DP. Big thanks for making things easy to understand.

@BackToBackSWE 4 жыл бұрын

sure.

@pallabjyoti 4 жыл бұрын

Liked...as soon as he finished teaching with the "aab" and "azb" strings. One of the most beautiful explanations I've come across. Thank you : )

@BackToBackSWE 4 жыл бұрын

great, thanks, and sure

@yicai7 4 жыл бұрын

The best video of LCS that I have ever seen so far You have a great talent, honestly

@BackToBackSWE 4 жыл бұрын

thx

@0the0ambient0 3 жыл бұрын

Great, clear explanation. Thank you!

@xoxo_kylie 2 жыл бұрын

I can never forget what i learnt from this video .. This is the power of your explanation and breaking down a complex problem into something so easy to understand.. Thanks a lot

@BackToBackSWE 2 жыл бұрын

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

@treygranderson148 4 жыл бұрын

I finally understand the thought process behind dynamic programming thanks to your diagrams and explanations. THANK YOU.

@BackToBackSWE 4 жыл бұрын

nice

@IlyaBoytsov-dt8lt 4 жыл бұрын

Thank you very much for your videos! Your ability to explain hard problems is fantastic! Please keep going!

@BackToBackSWE 4 жыл бұрын

sure

@warnercooler4488 2 жыл бұрын

Finally understood this. Thank you so much!!

@blwallace1 3 жыл бұрын

Awesome explanation! Thanks for being so thorough =)

@tirthdoshi7463 4 жыл бұрын

This is the best explanation I have received so far on this problem ! Thanks a lot !

@BackToBackSWE 4 жыл бұрын

sure

@rudrarajgohil2075 3 жыл бұрын

Great Explanation of Dynamic Programming with its example. Keep up the good work.

@harold3802 3 жыл бұрын

Thank you so much, I have gotten an intuition of how to do dp problems through your videos. The explanations are simple and easy to follow.

@BackToBackSWE 3 жыл бұрын

great to hear

@adrianharo6586 4 жыл бұрын

Best LCS video on youtube hands down. Thank you my dude

@BackToBackSWE 4 жыл бұрын

thx

@dewalchaturvedi7240 3 жыл бұрын

The best explanation of LCS Problem I have ever seen. This guy is amazing!

@BackToBackSWE 3 жыл бұрын

thanks

@andrewleonard5727 5 ай бұрын

This was an insanely good explanation. Much better and more in depth than my graduate algorithms course. Thank you!

@gurmansingh1878 2 жыл бұрын

Great Explanation ....Hats off to you..!!!

@chaengsaltz829 2 жыл бұрын

Fantastic explanation! Thank you so much!

@joels978 4 жыл бұрын

awesome awesome awesome. Really took the time to explain the nuances. much appreciated!

@BackToBackSWE 4 жыл бұрын

sure

@LoneWolf. 5 ай бұрын

Your teaching style is best. Why am I saying this? When you were going through the explanation the moment I was falling in confusion you were just there to tell "wait, this might be confusing but I will explain". This gave me the confidence and continued. DP was a nightmare to me. I just got what I wanted. No words to thank you enough. I am from Bangladesh, and I want to say my gratitude, man! Amazingly great explanation.