19 Longest common subsequence Recursive
Vložit
- čas přidán 4. 02. 2020
- 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.geeksforgeeks.org/longest...
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
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 !!
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 😂😂
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
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.
Now i got why you are SDE in Flipkart. You are awesome man.
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.
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 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!!
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.
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!
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
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
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.
You are the hero that we need, but don't deserve. Thank you so much for this content.
Thanks bro. I was so afraid of ds, algo. But because of your teaching I've overcome my fear to some extent. Keep growing!!!
this channel deserves all the love there is in the world!!
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. 😍🙌
Excellent Explanation !! .. Thank you so much !! ..Best DP explanations so far on CZcams.
oh man, your teaching style is just too good, pls make the same content for trees and graphs too
The best way of teaching using just pen and paper. Thanks for teaching!
One day I want to solve questions like you do and with your clarity and understanding level.
Simply awesome!. Never seen anyone explaining so well like you do Aditya!.. Amazing!..
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
the way you breakdown each and every key term is very good very few youtubers focus on this. 😍
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 🤘🤘
thanks a lot aditya, ab toh aage yeh problem khud hi hojaegi, all credit to you for this confidence!
You make everything easier than I used thought. Best dp tutorials!!! Thnks a lot🙌
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.
You are just amazing!!!❤
Can't thankyou enough for such amazing explainations!
Really thankyou very much, you made DP the best!🙌
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 .
shabd kam hai apke liye..... One of the best teacher!!!!!
Amazing teaching sir. Beyond appreciation. Please don't stop posting videos.
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
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
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.
this whole series is a gem
Bhai jaha tak.mene search kara hi dp youtube me ,,abhi tak aisa channel nahi mila ...thanks a lot
I wrote the solution with my own by using the concepts you taught in previous lectures. Thanks you so much
Thank you for putting so much efforts in putting these solutions and most importantly teaching them the right way.
keep doing this good work... please start graph also
Such a good video.. Dynamic programming is really hard and confusing concept. The way u explained the concepts, made it look easy
nice of you to go through the whole process !
I solved it myself. All thanks to you. You are the best.
Your videos are very easy to understand and also cleared many misconceptions I previously had. Thank you very much
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 💯💯
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 ?
you wont find a better explanation for LCS anywhere. Thanks a lot aditya!
Brooooo you're the best!!! Please add videos on DP on graphs and backtracking also!!!! Thanks a ton for your effort!!
my trainer recommended me your lecture. Your approach to the problem is good
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.
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.
sir,,,you are awesome... bestest tutorial of DP
Best DP course on internet!
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.....
thank you sir, great explanation.
u r the best guide one could ask for... lots of love
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 !
Excellent Explanation
Thank you Aditya Verma
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. 😛
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
literally! the best . strongly recommended for first year and second year students
I was able to solve this problem on my own because of your previous videos THANK YOU
Beautiful work. Thank you.
Best of the best of the best. I am preparing for Amazon, JP Morgan Chase Interview. Helps a lot Thank you
Awesome explanation, very intuitive explanation with choice diagram and base case.
Seriously man! this was the best explanation of LCS at CZcams!!! 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 CZcamsrs 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.
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.
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 !!
awesome and simple explanation!! THANK YOU SO MUCH
Your teaching style is awesome, Aditya. Please provide some tutorials on Kadane and LIS too
Done this question with the intuition of edit distance and it got accepted in gfg thanks for another approach. Bro your videos are lit 🔥🔥🔥🔥🔥🔥🔥🔥🔥🎉🎉🎉🔥🔥🔥🔥🔥🔥🔥🔥
REally really nice tutorial!!!!
Thank you for such a great job !!!
One of best tutorial bro .. hats off t you
The best explanation I have ever seen
Silver button on its way.. Congratulations..
Nice explaination brother. Please cover Graph and Trees as well. It would be really helpful to learn from you . Great concept clarity.
The best explanation i have ever seen. Thanks Aditya Bhai
cant describe in words Great Explanation!!!!
recursion toh jadhu hai bhai...love you bhai
Very nice teaching style!!
Wow.. You are really talented teacher... Great explaination👌👌
thank you.Your contents are just masterpiece
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!!! :)
Esa content kahi nhi dekha ek number !
I am able to develop this solution by my own because of you 😊thanks brother
You are a teacher material ❤️
Sir your teaching style 110/100
You made me fall in love with DP!
very very nice teaching unlike others who just come type code and just read out that
the way u teach , I can never forget any concept
Hi, I think you should also mention the algorithm complexity of both(recursive and dp) solutions also.
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