Hi, everyone.
So in this video, what we are going to do, we are going to write the deep solution for this problem,
longest common, subsequent.
So what we need to do, we just need to convert this recursive code into our DP are.
So that's going to be very, very simple.
For example, you are with two things, apple and mango.
So what I will do, I will take one string like this.
I will create a Julietta.
I will create one today and I will start from I will start from zero to zero, and then we have Apple.
And similarly, zero, and then we have him go.
So what we are going to do is we will define DPO.
So what Deepthi means so deeply offensive means the longest common subsequence between two strings,
between two strings as to an end as two.
And we are considering i.e. correctors.
For S1.
I characters of Esswein and characters of string, too, right, I'm repeating myself, if I'm not clear
so what the prophecy will contain so deep.
Viji will contain the length, the length of the longest common subsequent four i.e. characters of S1
and the characters of S2.
So in that case, what will answer?
My answer will be DPE of Emelin.
What is so basically this last box, so what is M m is basically the number of characters in the first
string and is the number of characters in the second string sample.
Right.
So it's going to be very, very simple code.
So let's just start writing the code.
So what do you need to do?
First of all, let's comment about this part.
So we need to create one to Ledbury.
So entity and virtual with the size, the answer is and then the array will be of size and plus one
and end plus one.
Right.
And what is Emelin so m is basically let's change the string name here, needs to make it Esswein and
let's make it as two.
So what is missing number of characters present in the first string.
So as our Lord says.
And and there's the number of characters present in this second string, so as to our size and our answer
will be DPF and then so what is the payoff?
And.
So it's very simple.
It is basically the longest the length, the length of the longest common subsequent when we are considering
M characters of string one and end characters of string two.
And that is where the question asked us to do.
Right.
So let's start filling this area.
We will fill this area.
So we'll see if the first string is basically empty.
Then the longest common subsequent will be zero.
So there will be zero.
If my any other string so out of the toasting, if one string is empty, then your output will be zero.
Right.
So if the first thing is empathy, long term subsegments will be zero.
If the second string is empty, your longest common subsequent will be zero.
So that's the best case.
Exactly what you have written here.
Exactly that.
So let's write that.
Let's first do let's first iterate over this area and we will consider this case also.
So I need to fill this area starting from zero.
Am I plus.
Plus.
So here's what I'm going to do is I'm going to fill this, Eddie.
So let's first talk about base case, so base case, it's very simple if any of the string does not
exist.
So if I equals zero or Jaquiss zero, that means if one on the string does not exist, one of them is
predicting either one is assembly or the string, too, is empty.
In that case, the longest common subsequent is going to be zero acres of land.
Zero.
Simple, right?
And after this, for Lluvia going to return you around answer, which will really be off and then as
discussed.
So apart from the base case.
We discussed there will be two cases, match or mismatch, so this is the matching condition, right?
So if we have a match.
Match means, as of eye is Ezequiel's to as two of G.
That means we have a match.
So in case of match our answer will be our answer will be one plus B of A minus one and G minus one.
Simple right.
In case of mismatch.
So in El Spart, if there is a mismatch then DPF.
Then the apology will be the maximum of.
DBF I minus one, Angie.
Plus, both I and G minus one and that.
That's what you need to do.
So let me explain you again, so what I'm doing, I am first finding out this is for both the strings,
then I'm creating this disparity of M plus 100 plus.
And because evidence is going to be the length of the longest common subsequent.
So when we are considering M characters of String one and end characters of string two.
Simple.
So we are iterating over this area, right?
We are all of this debris and while iterating this is our best condition.
So if any of this thing does not exist, then your body will contain zero.
Basically the length of the longest common subsequent will be zero.
Right.
Otherwise, if there is a match, if there is a match, then your answer is going to be one plus I minus
an engine, minus one.
Right.
If there is a match, then your answer will be one plus this value, whatever the value has been stored
in this box.
Otherwise you have two options.
If I am innocent or I and G minus I'm sorry I have written plus here it should be comma.
Right, so let's do that.
So it will be maximum of two things exactly like this, right, exactly like this, maximum of two things.
So here we have done one mistake, and that mistake is basically so that mistake is basically so if
the value of A is M and if the value of G is N, so what they are doing as often as one of em, which
does not exist, the last index is basically Asanov, I mean add because the indexing starts from zero.
So instead of comparing G, what should I do.
I should compare I minus on energy minus one.
Right.
So let's do the correction here.
So it will be a minus one and G minus one.
Now our code is correct and our code will work now.
So let's submit our code and see with our code will work or not.
So let's try to let's try to submit our code.
OK.
So I'm getting runtime errors and so we did some mistake.
What is the mistake?
OK, so I have understood what is the mistake.
So what I'm doing here is, see, I have written if it should be elusive because see if the value of
is zero, what will happen?
I will check this condition.
And what does this condition this condition is?
ASANOV Zero minus, and that is Asanov minus one.
So I should write here instead of writing.
If so, let's correct our code.
So we should write here as if instead of writing if now code is correct.
So our goal is working fine now.
That was a very silly mistake that we have done.
So let's discuss time and space complexity for this problem.
So it's very obvious that the time complexity.
And space complexities, so space complexity is basically you are creating one bit of space and listen
to the space, complexity is basically big of M.
Cross and light, and similarly, what is the time, complexity, so you are trading over your right,
you are trading and then this is basically constant work.
So time, complexities and then multiply.
And so this is the time and the space complexity for this problem.
Right.
So that is all that I want to discuss in this video.
So this is it, guys.
I will see you in the next one.
Thank you.