19 Longest common subsequence Recursive
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- Longest Common Subsequence Problem solution using recursion
Given two sequences, find the length of longest subsequence present in both of them.
A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.
For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”.
PROBLEM STATEMENT LINK: www.geeksforge....
Playlist Link: • Dynamic Programming | ... .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
bro, you will go way further if you take the path of teaching programming. I have seen alot of tutorials ,some paid and some free content in youtube. But no one teaches programming like you do. It's because you are teaching how to think like a coder which is very rare. Keep it up.
Thanks brother, Do subscribe and share, that keeps me motivated to do more !!
@Jacob Noe fuck you scammers, google shows your scams
@@TheAdityaVerma bro you should mention in every vid that you have mistaken top-down for bottom-up, this will help your channel grow more, bcz jo bina recommendation aaye honge wo log vid shayad puri hi na dekhe soche ki galat pdha rha h, ik unka bad luck. But you must add a frame or something else in each vid about this correction!
Can anyone explain why we increase the length by 1 when we have common character in both the string? I mean there might be a case wherin the LCS doesn't have the same character but we included it in our solution
@@sachinarora6682 because we need the count like how much is common. so if there is a match we have to count somewhere to get the count as 4.
if there is no match it will not come inside that condition and answer would remain 0 hope you are talking the one explained at #23:11
I genuinely request all others to watch his lectures by disabling Adblock(if u have any)!!! It's worth it supporting this channel! Its light years ahead of other lectures!!! Thanks a lot Bhai for the content!!!!!!
Brother, This comment is love ❤️ Its really hard to find guys like you these days. Respect !!
thanks for giving idea of using adblock
@@bhavikmehta7193 lol
I do the same... keep the ads coming :)
@@binod3204 binod spotted 😂😂
Brother you'r red coder in teaching programming.
Can anyone explain why we increase the length by 1 when we have common character in both the string? I mean there might be a case wherin the LCS doesn't have the same character but we included it in our solution
@@sachinarora6682 we would only increase that if there's a match. because if theres a match than definitely we would have something in common. if there's no match we will return for the rest of the substrings.
@@sachinarora6682 we increase length by 1 as we know the first common character from the end will definitely be in the longest common subsequnce. This is due to the fact that we are looking at it from the end and not the beginning. So no matter what the length of the LCS is between x[0....n-2] and y[0.....m-2], if you add the last common character among the strings (which is x[n-1]) it will create a longer LCS with length one greater than the previous LCS. I probably think you have mistaken subsequence for substring but by looking at your other comments, that doesnt seem to be the case. Just think of it like this -> Prefix substring of x[0...n-1] iis equal to x[0...n-2]. Let LCS of prefix substrings of x and y be of length L (assume it is the most optimal i.e longest subsequence). Now, if the suffix characters are equal (i.e x[n-1]==y[m-1]), then they can be added to the LCS of the prefixes to make a "longer" LCS and this "longer" LCS will be the LCS of the full strings x and y. Simple as that :D
Bhai currently I am working at one of the MNC but one thing I learned that to survive in IT sector you just cannot stop practicing DS Algo, I always was a little weak in recursion and had no idea about DP. Even during placement season I somehow memorized first 20 Standard DP questions from geeks, but since the day I started watching your dp playlist, I must admit my life has become easier, recursion and DP feels too easy. Kudos to you . Thanks a lot.
Thanks brother, If you like the content please do share where ever you feel right to help the channel grow !!
Hands down best DP tutorial ! I'm so glad the number of subscribers are increasing everyday
I am glad you think so !!
19 of 50 (38%) done! Very good explanation and revision of recursion steps. It has become so easy that I can tell what you are going to say next -- it means you taught very well in earlier videos :-)
i am following the lectures with you, bro
I could actually write the solution on my own by deriving from the concepts taught in Knapsack. Thank you so much for these tutorials. Wish you the success that you truly deserve.
Exactly that's what i was gonna write here😂😂 his teaching skill is awesome ❤️
Same DP seems easy now, but Ill have to work on recursion now.😂
@@thisishunayn Coin change problem: Minimum number of coins
agreed. he teaches in a way that you develop your intuition about dp
Now i got why you are SDE in Flipkart. You are awesome man.
The guy who has made the dp easier is the Aditya Verma..... He has made the dp like halwa. Concepts are too easier to understand. Thank you Sir.
The pens you use sound so satisfying 😍
You should bring out your ASMR series too with them 😂
I have never seen a neat technique like this to build recursive solutions! You should teach backtracking as well in the same way! I could always build recursive solutions by building up the whole call stack in tree format and then identify "choices" and "base cases", but I see how you can "abstract" this thinking out.
Your technique is also better because sometimes, you might have a really huge call stack tree, depending on inputs you choose to come up with recursive solution.
Bought *GFG Paid DSA Self Paced* course it is slow as fuck, I will not say it is not good but man nothing compared to this.....You made me feel that I am able to do coding. Else I was feeling like a crap for almost a year now. Thankyou and love u brother.
Bhaiya ,your knapsack explaination is so good that I figured out this question in just 5min of starting.....thankyou bhaiya my thinking skill in recursion is increasing
If anyone is thinking examples like in strings abcd
and abedcg , what is the length of longest common subsequence, if you're thinking that LCS length here is 4, as a,b,c, and d all are present in both the strings, then you're wrong... Because--" A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous." I had the same doubt. Hope I helped someone. Peace out!
Hands down the best LCS tutorial on all of youtube!
Abe ye dislike walo sharam karo thodi. Itna effort lagake ye video bana raha wo bhi world class, bc na to tum support karte ho ulta dislike kar dete ho. @Aditya Bhai keep it up. We will always support the good deed (And please Complete the series with missing and private videos.
I came here after watching Recursion Playlist to iska recursion design karna was a piece of cake as you promised at the end of the playlist. Thank you very much. God bless you.
I suggest you, open your startups like scalar academy, Bhai tu un sb Microsoft, google walo pr bhari padega..
aaram se bhai
@SauRabh_50 kaise jyada bhai ?
the way you breakdown each and every key term is very good very few youtubers focus on this. 😍
Thank you very much sir . Sir main iss video ko 2022 mein dekh raha hoon, lekin jitna simplify karke aur thinking approach aapne bataaya hai, utna mujhe aur kahin nahin mila.
shabd kam hai apke liye..... One of the best teacher!!!!!
I seriously can't believe how easy it was to understand this just because of the previous videos. You rock man! 😎🙇♀️ Thanks a lot for such amazing videos. 😍🙌
with so much dedication and passion I have not seen anyone teach like this its like my elder bro is teaching me a big Thanks to you, mera dp ka daar dur karne ke lea
One day I want to solve questions like you do and with your clarity and understanding level.
Such a good video.. Dynamic programming is really hard and confusing concept. The way u explained the concepts, made it look easy
oh man, your teaching style is just too good, pls make the same content for trees and graphs too
Discovered underrated channel . Thanks :)
Thanks bro. I was so afraid of ds, algo. But because of your teaching I've overcome my fear to some extent. Keep growing!!!
Over 1 lakh views and only 3.8k likes :(
This guy deserves more likes guys because of this wonderful explanation for the whole dp series.
thanks a lot aditya, ab toh aage yeh problem khud hi hojaegi, all credit to you for this confidence!
I have read articles on LCS many times , but the way you taught LCS ..it was just great...keep it up big bro never stop.
I have never liked DP this much.I have solved most of the DP questions in these two days after watching your videos. Great work!!
Hey bro, I have a request for you that if you are not able to make videos of the remaining topic of DP then please provide us notes of the remaining questions of DP.
you are amazing bro, everyone says that DP is the toughest topic in coding but in which way you are teaching us, it is not looking that tough.
thanks bro.....
Seriously man! this was the best explanation of LCS at TH-cam!!! I watched other guys like Tushar, Jenny and sir Abdul Bari & was disappointed that they started explaining the algorithm straightaway instead of focusing on the approach.
I personally hate those TH-camrs who start their videos by explaining the algorithm instead of building the approach to get that.
You're gonna go heights with this way of explaining. The thing I like about you is your on-spot approach. No language bullshit etc...keep it up.
Bhai jaha tak.mene search kara hi dp youtube me ,,abhi tak aisa channel nahi mila ...thanks a lot
You are the hero that we need, but don't deserve. Thank you so much for this content.
very very nice teaching unlike others who just come type code and just read out that
These Questions were like a nightmare to me, but because of you, I designed a top-down version of this question on my own.
Thank you, bro.
Ur explanation, of subsequence vs subarray, just shows that u r teaching from the ground up, without presuming that people will understand it anyways. Amazing 🤘🤘
Really thankyou bhaiya due to ur teaching i was able to write all the three approaches recursive, memoization, tabulation for this problem earlier lcs problem were nightmare for me
This is only possible because of u❤❤❤❤
Awesome teaching of coding there are many institutions that take huge 💰 but not teach even 20percent of ur quality teaching ....Bro U make course on compitative coding(complete) that ill make ur channel...grow in million believe me.....
You are a great teacher. Your teaching method and flow is very easy to understand. May shree ram bless you and you may attend all the success in life.
Bhai knapsack dekhne ke bad and uspe questions krne ke bad, iski choice diagram, maine khud se banai and bad me tumhara video dekha to maine ye paya ki mera brain evolve ho chuka hia. bro.
Bahut acha lag rha ma kasam
Maza aagya
keep doing this good work... please start graph also
Amazing teaching sir. Beyond appreciation. Please don't stop posting videos.
The best way of teaching using just pen and paper. Thanks for teaching!
I was able to solve this problem on my own because of your previous videos THANK YOU
Ioved your teaching approach I hope you know every bit of technology everything, so that you break it down for us. I have been trying to get my head on machine learning if there is any chance you coming up with lectures! 😇 Or recommended me some your best pick course on ML.
Bro, after watching your videos I feel I can also solve problems in DSA.
Before , I was not able to solve a singel question in DP.
Keep up the good work.
Salute to you ...
Make some videos on graph.
I wrote the solution with my own by using the concepts you taught in previous lectures. Thanks you so much
Hey, this is a great content hats off to you for that, but what I feel you should add more is ,why these problems fall in the DP category.
this channel deserves all the love there is in the world!!
you wont find a better explanation for LCS anywhere. Thanks a lot aditya!
my trainer recommended me your lecture. Your approach to the problem is good
Hi, I think you should also mention the algorithm complexity of both(recursive and dp) solutions also.
Bro your teaching skills are great ❤️.Please come up videos covering all the DS algo topic .we really need it .You are better to then any course either paid or free
I feared these kind of LCS derivatives, I on my own developed the right intuition to solve this one using previous problems, felt so good !
I was struggling with LCS for quite a long time. You really cleared it up. Thanks. Keep it up. One feedback though. Please mention time and space complexity as well.
this is the best lecture of LCS this is really really helpful for the beginner in programming thank you so much for this amazing DP series 💯💯
Best of the best of the best. I am preparing for Amazon, JP Morgan Chase Interview. Helps a lot Thank you
Kya mast sikhaya bhai ! I wish I could tag my imbecile teachers here. They should learn from you. You definitely know how to break down concepts easily. Aditya Verma supremacy !!
Your videos are very easy to understand and also cleared many misconceptions I previously had. Thank you very much
Big Fan Sir!! apka "SUM UP" Style bahut achha he !!! itna achha ki sirf sum up bhi dekha to bhi sab kuch samaj a jaye!!! :)
I guess Memoization is TopDown Approach. Please correct me if I am wrong.
Loving the content you put out man! Please also put out a series on Graph problems as well :) I feel knowing BFS, DFS is different from actually applying them in the problems like number of islands etc.Please make a series of videos on them as well
Brooooo you're the best!!! Please add videos on DP on graphs and backtracking also!!!! Thanks a ton for your effort!!
Due to your teaching style chuma Dene ka mn kr raha 😅.currently I watch your video in 2023 and I miss you big brother 😢 because of your inactivness on youtube.
Thank you for putting so much efforts in putting these solutions and most importantly teaching them the right way.
bro, please come with complete tree and graph series, we will be okay to pay for a cohort based teaching too.
Literally I'm addicted to your dp playlist
literally! the best . strongly recommended for first year and second year students
nice of you to go through the whole process !
Bahi m wo gadha hu jo recursion chala k dekh ta h 😂😂😂😂😂 thanks a lot keep it up
😂😂 koi na bhai !! kbhi me bhi thaa 😕😂 actually shuru shuru me sb hote hai 😅✌️
Do share the content if you like it and help the channel grow !!
Simply awesome!. Never seen anyone explaining so well like you do Aditya!.. Amazing!..
I had watch lots of lecture of recursion and dp but I always be confused in these topic but watching these video lecture series made me clear each concept of recursion & DP from basic to advance level
sir,,,you are awesome... bestest tutorial of DP
I solved it myself. All thanks to you. You are the best.
I think it should be y[m-1] instead of y[n-1] at 21:51 BCOz length of string y is m
correct
u r the best guide one could ask for... lots of love
Silver button on its way.. Congratulations..
this whole series is a gem
Excellent Explanation !! .. Thank you so much !! ..Best DP explanations so far on TH-cam.
9999 ^ 9999 likes for this explanation. I could have never imagined that LCS can be this simple. Thank you.
Bhai apka parhane ka style bht acha.
Aditya - You rock brother. Like you say "Fear no more .. Main hoon Na". A suggestion to create a patreon link so that people can payback if they wish, like me. Your way of teaching is quite good.
Thanks man, appreciate it. 🙌 🙌
I do have a patreon page: www.patreon.com/adityaVerma
@@TheAdityaVerma ohhhh you are alive. Just kidding 😁😁
Sir your teaching style 110/100
Thank you so much for such a great explanation and jokes "aaj mere saare pen khatam ho rahe hai!!"
the way u teach , I can never forget any concept
You are just amazing!!!❤
Can't thankyou enough for such amazing explainations!
Really thankyou very much, you made DP the best!🙌
Fantastic teaching bro... I was terrified of DP... Now they have become way simpler.. grateful to you
I guess people will be willing to pay for these videos.
I have downloaded the playlist just in case. 😛
Awesome explanation, very intuitive explanation with choice diagram and base case.
recursion toh jadhu hai bhai...love you bhai
I am able to develop this solution by my own because of you 😊thanks brother
Your explanation is very very good bro i appreciate your hard work , can you please also make a playlist on recursion .
Thanks and already have made one
@@TheAdityaVerma oh i see......thnks🤍
mja agaya bhai pura data structure cover karlo aisehi bas . paise leke start karo leking jaldi start karo.
its amazing all ur lectures are far better than any other content i have ever seen regarding programming. Hope to see more contents from u.. I am aiming to finish ur each and every playlist .
When would you complete this playlist? I have been relying on this to gain my DP knowledge. Please complete it. Thanks for all the tutorials you have created. Much appreciated
Done this question with the intuition of edit distance and it got accepted in gfg thanks for another approach. Bro your videos are lit 🔥🔥🔥🔥🔥🔥🔥🔥🔥🎉🎉🎉🔥🔥🔥🔥🔥🔥🔥🔥
The best explanation i have ever seen. Thanks Aditya Bhai
You make everything easier than I used thought. Best dp tutorials!!! Thnks a lot🙌
Excellent Explanation
Thank you Aditya Verma