Hi, everyone, welcome to this new video.
So in this video, we are going to solve one question and find out the longest common subsequence between
two strings.
So first of all, let us try to understand, what do we mean by a subsequence?
So far, this string, the subsequence can be Eppy.
It can be easily.
It can be E, it can be B. It can be B, B and so on.
So now we know what is the meaning of subsequence.
So given to string, first string and the second string, we need to find out the longest common subsequent
between them.
So in this case, the longest common subsequence will be E and the length is one rate.
So E is present here is also present.
Here is the longest common subsequent and the length is one.
So we need to return the land.
We need to return the length of the longest common subsequent.
Let's talk about this example.
So we have a we have it then we have this B soapies here then.
And so Elly's here.
So in this case, the longest common subsequence is basically A, B, L and E.
So my answer will be for.
Right, so a U.S. president here is present here, B.L. is present here and police present here.
So that's why Epperly is the longest common subsequence of land for.
So our answer will be land for now.
Let's talk about third example.
Apple and this word, this random world, so we have a we have A we have E, so we have it here and
yes, so in this case, the longest common subsequent is basically E and E, so e e and this is A.
So the length is basically two.
So in this case, my answer should be to the length of the longest common subsequent is basically two.
So I hope you have understood the problem statement.
So how we can solve this question so we can easily solve this question with the help of recursion,
how the will help us.
So let's consider two strings.
So this is my first string apple and this is my second string mple.
Right.
So what I will do.
Let's take one variable I here.
Let me reiterate again, so I have this string apple and I have an added string, which is Apple, so
take two indexes index xiphoid rating in order for a string index for our trading over the second string.
Now, I ended the article.
So this match there is match, match means I got equals.
So if I and the guy recall what we do, we will tell Dacogen, find out the answer for this part and
this part.
So my answer will be, I have one I have one common character between these two.
Samantha will be one plus the longest common subsequent between this string and this string.
So I will call the function longest common subsequence.
Let's say this is string one, this is string to string one, and the rest of the string of the string
is a plus one.
Similarly, string two and rest of this string find out the longest common subsequent between the rest
of the string.
So J plus one, if there is a match, then in that case this will be my answer.
Fine.
So what this function will do, this is a recursive function.
This takes two string as input and it gives us the longest common subsequent Slint.
Right.
So what I'm doing here is if the character matches, if there is a match, if there's a match, then
the answer will be one because there is a match then and case of rest of the string.
Similarly altius of the rest of the string.
Now if there is no match.
So if we do not have a match in case of mismatch.
So let's take one example here.
If I have this, let's say this is one string and we have another string, let's say this one.
So we have these two string.
I is here, G is here.
This is string one.
This is string two.
Now if we will compare so string I is not close to string.
So the correct that I is not close to character G so this is the case for mismatch.
Right.
So we have a mismatch here.
So in mismatch we have two possibilities.
We have two possibilities.
First is I will tell recursion.
To find out the answer for.
To find out the longest common subsequent between the m'appelle and.
M'appelle and the second possibility is find out the subsequence between Apple and Apple and repeating
myself, I'm going to compare AMG so Iyengar different.
That is mismatch.
So in case of mismatch, I have two options.
So the first option is basically I will tell the commission to find out the answer for this string.
And this is string.
So that's why m'appelle the entire string and this reduced string emboli, so in this case, what I'm
doing, Stringbean and I will not string two and G plus one, we need to pass the rest of the string.
So J.s here, we need to pass that statistics of J plus one.
The second option is what we will do.
So second option is take this entire string, take this entire string and reduce this string.
So reducing the strength will become a both and we will take this interesting, so this is ample.
So in this case it will be one and the string and the string two will remain the same.
So it is useful to tell me the length of the longest common subsequent similarly for this also and will
determine the length of longest subsequence.
So in this case, where to leave?
My answer, my answer will be zero plus zero because there is a mismatch, right?
Zero because we have a mismatch here.
Zero plus I have two options, so I will take the some of them.
So I have two options.
Let's say this is first option.
This is second option.
So the maximum of option one and option two, that will be my answer.
Simple, right.
So I discussed both the cases in case of match the this is our recursive formula in case of mismatch.
This is our recursive formula.
So this question is basically present on netcode, longest common subsequent.
So what we are going to do is let us first write the recursive approach for solving this problem.
So let's start writing the code.
So we have a function, the function will return the longest common subsequent, so let's say the name
of the function is is what it takes.
It takes two strings, right?
So string S1.
And its index similarly string as to and its index.
First of all, we need to discuss about the base case, so this case is very simple.
If I is basically Esswein darte size.
Or, gee, is it close to a the size then in that case, what will be the longest common subsequent?
It will be zero.
So if string one does not exist or string two does not exist, then in that case, if one of the string
does not exist, then your answer will be zero.
You cannot find longer term.
And subsequently, if one of the string does not exist simple right now, what are you to do?
You need to check whether there is a match or mismatch, so let's check in case of match.
So that is as of I will be equal to as two of you.
So, yes, there is a match in case of match.
What is our answer?
Our answer is one plus and is off.
We will pass since is a match.
So when plus we need to pass the rest of the string.
So rest of the string is Esswein and IHI plus one as two and G plus one.
Simple.
Right.
And in case of mismatch.
So in case of mismatch.
So this is the case for match in case there is a match and this is the case for mismatch.
So in mismatch, what we're gonna do is we will, our answer will be zero plus or let's not write zero
plus.
Let's simply write Alex off.
I have two options here, right?
I have two options.
The first option is S1 and I and J.
Plus one.
Second option was Altius off S1.
I plus one, and as to gee, these are the two options that we have and we need to find out the longest
common subsequent right.
We need to find our longest.
So we'll take the mix of them.
So we'll take the maximum of two possible options, myxoma first and second option, that will be our
answer.
Right.
So, yeah, that's the complete code and let us call this function string.
So I did it on Altius.
It takes string one, which is one I will start from zero, obviously, string two, which is text two,
and I will start from zero obviously.
So yeah let's FirstRand our code and then we will submit.
So, yeah, our solution is working fine now, something called.
So basically, we are getting timely redecorated, and it's obvious because this is recursive solution,
right?
This is recursive solution.
Our solution is correct.
Our solution will give the right output.
But this is a recursive.
So that's why we are getting timely and excited.
So what do we do in NextRadio?
We will write the dynamic programming code for this problem.
So if you want, you can try writing the code yourself.
Otherwise you can watch the next redo.
And in the next video we will convert this recursive approach into dynamic programming code so that
from this device.
I will see you in the next one.
Thank you.