Longest Common Subsequence | Recursion | Memo | Optimal | Leetcode 1143
Вставка
- Опубліковано 26 сер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 10th Video of our Playlist "Dynamic Programming : Popular Interview Problems".
In this video we will try to solve a very good and famous DP problem - Longest Common Subsequence (Leetcode 1143)
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Longest Common Subsequence (Leetcode 1143)
Company Tags : Microsoft, Amazon, FactSet, Hike, Citrix, MakeMyTrip, Paytm, VMWare
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approach-1 Summary : The approach uses a recursive approach with memoization to avoid redundant computations. The memoization is achieved by maintaining a 2D array t of size 1001x1001, initialized with -1. The function LCS recursively computes the length of the LCS by comparing characters of the two strings. If a subproblem's result is already memoized, it is returned directly; otherwise, the LCS is calculated, and the result is stored in the memoization table. The final result is obtained by calling the LCS function with the lengths of the input strings and initializing the memoization table before starting the computation.
Approach-2 Summary : The approach uses dynamic programming with a 2D vector t to store intermediate results. The code iterates through all possible pairs of indices, filling the table based on the recurrence relation for LCS. The final result is the length of the LCS for the entire input strings, stored in t[m][n], where m and n are the lengths of text1 and text2, respectively.
Approach-3 Summary : It utilizes a 2-row 2D vector (t) to store intermediate results, reducing space complexity. The code iterates through the strings, updating the table based on the LCS recurrence relation. The final result is stored in t[m % 2][n], where m and n are the lengths of the input strings. This optimization maintains the same functionality as the original code but with reduced memory usage.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear
Your way of explaining things out is really awesome brother. Keep it up and please keep uploading videos, you will surely be successful !
Thank you so much Aditya ❤️❤️❤️
true
indeed
You are best!!!!
And so are people like you.
Thanks a lot Shashank ❤️❤️❤️
Hi Mik, I had done this question earlier through some other explanation by some other UA-camr. Today I saw this question again and totally forgot how to solve it. I searched for your video and trust me when I say this, i will never forget the solution now because now i UNDERSTAND how it works intead of memorizing it.
You make it incredibly easy to 'understand' the underlying algorithm. Keep posting videos, you are an extremely good teacher.
Teaching is an art, and you are Picasso!
Thank you so much.
Glad to know it helped 😇❤️🙏
Your teaching is working so well, your method of solving is sticking with me. I didn't even understand recursion well a week ago and today I watched your explaination and coded the solution myself and I'm so proud of it.
Thank God that I found your channel and such an amazing Teacher
You just made my day ❤️❤️🙏🙏
I feel so relaxed after seeing such comments. The main motive is to make people understand that these can be done easily once you understand the core behind it. Thank you so much for sharing ❤️❤️🙏🙏
yes, for me too
💯
indeed
Just like Instagram, I come to MIK's videos to see the comments. And this is so true. I feel lucky to have found this channel a year ago.
bhai good one.
Thanks a lot ❤️❤️❤️
The best part that I love about your video is that you tell the reason for doing every step. This helps understand the intuition and logic easily.
The way you explain the recursion tree that alone becomes enough to solve the problems
🙏🙏😇
Literally the best one so far...
Thanks a lot Riya
Thank you bhaiya for such nice explanation and very easy to understand . I saw many youtube channel but your way of explanation is so nice that it tells all what is happening in the code 😊
So nice of you 🙏😇
GOD OF DSA
bhai if possible web development bhi sikha doo !!
dsa tho OP
Thanks a lot Rohit.
Sure I will plan for that soon.
Thanks again for watching ❤️❤️❤️
Really Great explaination ! I found your channel from gfg comment section
Thank you so so much Arnab ❤️❤️❤️
I watch other videos on youtube but those videos explanation is not even close to your explanation.❤
Question was HARD but MIK made it EASY.🎇
Thank you so much ❤️
@@codestorywithMIK Thank you is something which we want to say it to you for your work.🙏
❤️❤️❤️
Notes:
In every recursion problem we face we only have one index but here we have two strings we need to maintain 2 indexes for each of them
Now the main funda is which one to move how to move
If i say i move s1 index everytime then think of this case
s1 : abcd
s2 : fabcd
if i move s1 ahead then my new search space becomes
s1:bcd s2: fabcd
s1:cd s2: fabcd
s1:d s2: fabcd
s1:"" s2: fabcd
we got zero at the end but if you see carefully the answer for this "abcd" and fabcd" is "abcd" which is 4 but we got 0
conclusion i cannot only move s1 ahead✅
If i say move s2 index everytime then think of this case
s1:"fabcd"
s2:"abcd"
if i move s2 ahead then my new search space becomes
s1:"fabcd" s2:"bcd"
s1:"fabcd" s2:"cd"
s1:"fabcd" s2:"d"
s1:"fabcd" s2:""
we got zero at the end but if you see carefully the answer for this "fabcd" and abcd" is "abcd" which is 4 but we got 0
conclusion i cannot only move s2 ahead✅
So the only choice i have is i need to check for both of them once i assume index1+1 and in the other case i assume index2+1 where index1 corresponds to s1 and index2 to s2
Observations/Story
if s1[index1]==s2[index2] ----> we can add one to our count
else: we need to explore both the choices and get the best answer out of them or maximum as per question
We see some states are same we can memoize it as well
Recursion Approach: TLE⏲
class Solution:
def solve(self,index1,index2,text1,text2):
if index1>=len(text1) or index2>=len(text2):
return 0
if text1[index1]==text2[index2]:
return 1+self.solve(index1+1,index2+1,text1,text2)
else:
return max(self.solve(index1+1,index2,text1,text2),self.solve(index1,index2+1,text1,text2))
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
return self.solve(0,0,text1,text2)
Recusrion + Memoize :✅
def solve(self,index1,index2,text1,text2,dp):
if index1>=len(text1) or index2>=len(text2):
return 0
if dp[index2][index1]!=-1:
return dp[index2][index1]
if text1[index1]==text2[index2]:
return 1+self.solve(index1+1,index2+1,text1,text2,dp)
else:
t=max(self.solve(index1+1,index2,text1,text2,dp),self.solve(index1,index2+1,text1,text2,dp))
dp[index2][index1]=t
return t
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp=[[-1 for i in range(len(text1))]for i in range(len(text2))]
return self.solve(0,0,text1,text2,dp)
Done Thanks Mik i used to cramp LCS everytime Before i got to know your channel
But now i'm able to do 🙇♂❤
#storyToCode
This comment is a treasure 🔥🔥🔥
#storyToCode #codestorywithMIK
Awesome Awesome Awesome!!!!!
now i'm able to build tree by myself but it just matter of practice and i'm able to code it because i learn to make tree by my self and as usual able to findout the DP as well 🚀
Keep it up 🔥🔥
PURE GOLD!
I wish I had a teacher like you for my DS Algo class :(
❤️🙏
Thanks😊
You are truly amazing brother!!…just one doubt: do we have to give the bottom up approach in interview?…will giving only recursion+memo suffice?
Thanks a lot Adwait.
Actually as per my experience, interviewers ask bottom up also.
But always start with recusion
Then if they ask to optimise, do memoization.
Then further if they want, they ask for bottom up. I was always asked bottom up at the end
Nice explanation!
Aag laga diya bhai. Awesome explanation. you make things so easy
As always, great explanation 🔥🔥
🙏🙏❤️❤️
20:18 bottom up approach
This Channel - PERFECTION 🙏🏻
i always appreciate the intuition you make us understand
🙏🙏❤️❤️
This is the best explanation I have ever seen for this problem.
Nest level explanation bhaiya ❤
Very beautifully explained bro
Clearly explained!
Hats off 🙌
thank you
Thanks a lot bhaiya ❣❣
🙏🙏❤️❤️
nicely explained.
Thank you 😇🙏
You explanations are next level really
bas itni simple chiz ka itna hawva bana diye the log ? - *people after MIK drops a vid.
Thank you so much 😇❤️
lol , so true
Amazing explanation 🔥
Looks like the first solution with recursion+memoization is giving TLE at 46th test case.
Sorry my mistake. I was filling the array with zero. Which results in TLE
Mind blowing explanation 🔥
Sir first of all thank you for this lovely explanation
Btw sir can you please explain me in hindi why we are taking size of 1001(why not 1000) for the memoization case.
Hello
Humlog usually jab bhi memoization array lete hain to maximum size+1 islie lete hain so that out of bound waale cases me hamara code fat na jaae.
Ye ek careful step hai so that code break na ho.
Constraints agar 1000 hai to agar galti se recursion me aapne 10001 ka check kardiya to code waha break kar jaega. Islie humlog 10001 le rahe.
Lekin agar aap base case ko is tarah likhoge ki aap out of bounds na ho, then aap 1000 bhi le sakte ho
Thank you so much sir ❤
Sir, can you explain why we are adding t[i-1][j-1] ,
if(s1[i-1]==s2[j-1]) t[i][j] = 1 +(t[i-1][j-1]).
In video you told that we cann't add t[i+1][j+1] and it is resonable because we don't know the future values. But why we are adding t[i-1][j-1] is not clear.
first off all you should understand that what state definition says. It says that - dp[i][j] ==> LCS till index i-1 and j-1 or (you can say that till the traversal of strings text1 till i th index and text2 till j th index the LCS is dp[i][j] ) so we have to calculate the maximum or Largest Common Subsequence value so we should have to carry the maximum answer from previous (dp[i-1][j-1]) index..You should Dry run 2 - 3 Example with this code you will get it... -- hope it will help you :)
Please Also Explain Shortest Common Super Sequence Problem too, bro.
Yes @codestorywithMIK. Please.
Sir is it possible to solve with map?
Bhaiya tabulation method me agar hum last se solve karte aaye to last row aur col me kya initialize karenge
done
I tried using stack on it,storing them in two different stacks in reverse ....but that approach came out to be wrong because it does not try out possibility of skipping a character from other stack..while it only skips character from the stack which stores the longer string....
Indeed. I am glad you tried other approaches. It teaches us from our mistakes
public int longestCommonSubsequence (String text1,String text2){
if(text1.length()==0||text2.length()==0) return 0;
int m=text1.length(),n=text2.length();
int[]dp=new int[n+1[;
for(int i=1;i
I have one suggestion I have solved upto 200 questions in leetcode upto know I have identified this topics
IN Arrays
1.Binary search on answers
2.sliding window (2 pointers technique)
3.line sweep algorithm
4.And in dp there are so many algorithms like ( lcs,lis,dp on stocks ,knapsack,... )
5.in graph also so many algorithms ( by seeing your playlist we will know )
6.in trees (only do questions,bfs,dfs )
7.priority queue
8.stack ( ngl type of problems ,)
So apart from this do u know any common algorithms or patterns that helps to improve problem solving skills sir if u know please tell sir
wow. you seem to have already done a lot
class Solution {
public:
int dp[1001][1001];
int helper(string s1, string s2, int i1, int i2){
if(i1 >= s1.length() || i2 >= s2.length()){
return 0;
}
if(dp[i1][i2]!=-1){
return dp[i1][i2];
}
int ans1 = 0;
if(s1[i1] == s2[i2]){
return dp[i1][i2] = 1+helper(s1,s2, i1+1,i2+1);
}
int ans2 = helper(s1, s2, i1+1, i2);
int ans3 = helper(s1, s2, i1, i2+1);
return dp[i1][i2]=max({ans2, ans3});
}
int longestCommonSubsequence(string text1, string text2) {
// memset(dp, -1, sizeof(dp));
// return helper(text1, text2, 0, 0);
int m = text1.length();
int n = text2.length();
vector t(m+1, vector(n+1, 0));
for(int i = m-1; i >= 0; i--){
for(int j = n-1; j >= 0; j--){
if(text1[i]==text2[j]){
t[i][j] = 1 + t[i+1][j+1];
}
else{
t[i][j]=max(t[i+1][j], t[i][j+1]);
}
}
}
return t[0][0];
}
};
It will be helpful.
I have a question bhaiya if I take (string s1) instead of (string &s1) in the solve function to isme error kyu aa rha h?
Hello I have one doubt . In bottom up when element are not equal why are we taking max of only i-1,j and I,j-1 and not include i-1,j-1 while taking max. It just doesn't make sense to me why take max of only two values when elements are not equal. Please help I am stuck.
Bro how i access notes so that i practice from your notes.
Memoization konse video me samjhaya hai pehle bhai pls link dedo
Memoisation Explanation and coding starts from 2:57 and ends at 20:15
Which drawing app you used to visualize code?
if your code is giving tle then maybe you are not passing string as reference
Sir, Interview me top down or bottom up dono se solve karna padega kya ?
Or kisi v ek approach se solve kar sakte h?
I remember I was asked to solve by both approaches in one of the interviews i gave a year ago.
It depends a lot on the interviewer also.
I have a doubt brother where to use map for memoise and where to use vectors for memoise is their any thinking like when sum or targwt goes negative we use map for memoisation and not vector
Actually when the changing parameters (which you want to memoize) are good enough to make a DP array out of them, then use DP array to memoize them.
But in some cases, multiple parameters change and memoizing them with an array might require 3D/4D array, in that case I use map. Or sometimes, when we have string type parameter which needs to be memoized then use map.
But in one of MIK's videos, he taught that in many cases, you can actually get rid of extra parameters which need to be memoize and even sometime we don't have to memoize (when every state is unique), it opened my eyes about memoization.
Try searching for his video "Maximum Length of a Concatenated String with Unique Characters | Using Bit Magic" on UA-cam. He has briefed this thing.
will it be not a lot of wastage of memory by initialising dp[1001][1001] bcoz for smaller test cases it will be not good to allocate huge memory plz correct if I am thinking wrong or either by initialinzing array with any size doesn't matter in c++ ??
I totally agree. However, 1001 * 1001 is a small number as compared to other large constraints. You can go with this.
But I instead of this you can create vector of [m+1][n+1]
@@codestorywithMIK ooh yeah
btw your explanation is way better or best than many other youtubers👍...currently following your dp series
Why we need t[1001][1001] why cant we use t[n+1][m+1] size
Yes u can take this is also right
bhai aapne hi Einstein ko theory of relativity sikhai hai past mein aur fir aap time travel kr ke present mein aa gaye ho......bhai time travel krke btao ki future mei meri shadi kiise hogi aur jisse bhi hogi usne cycle chalai hai ya nhi🤣🤣🤣🤣....
😂😂😂
Video Quality Please check this also
Hi Manish, since the video is just uploaded, UA-cam takes few minutes to enhance the quality. Please give it few minutes.
Thanks for your patience ❤️❤️❤️
Recursion+Memo giving TLE.
Please share your code
@@codestorywithMIK
class Solution {
public:
int dp[1001][1001];
int help(string text1, string text2, int i, int j){
if(i>=text1.size() || j>=text2.size()) return 0;
if(dp[i][j]!=-1) return dp[i][j];
if(text1[i]==text2[j])
return dp[i][j]=1+help(text1,text2,i+1,j+1);
return dp[i][j]=max(help(text1,text2,i+1,j),help(text1,text2,i,j+1));
}
int longestCommonSubsequence(string text1, string text2) {
memset(dp,-1,sizeof(dp));
return help(text1,text2,0,0);
}
};
@@rushabhlegion2560 you need to pass the string by reference!
thank you bhai, i thought i won't be able to figure out why my code is giving tle. such a simple mistake@@theOmKumar
the explanation is damn sexy❤
Thanks a lot Manish ❤️❤️❤️
Damn
Thanks a lot Shashwat ❤️❤️❤️