Hello friends, my name is Tushar and today,
we're going to look at the question, Longest Common Subsequence.
What is this question? Given two strings,
how do we find the longest common subsequence between them?
So, for these particular two strings, "abcdaf"
"acbcf", the longest common subsequence
will be 'a', 'a', 'b', 'b'
'c', 'c', 'f' and 'f'.
So, the length of the longest common subsequence will be four.
and the longest common subsequence will be 'a','b','c' and 'f' , so, the thing with subsequence
is that
it need not be continuous in the string, so, here
'a', 'b', 'c' and 'f' and we ignored 'c', and above
'a', 'b', 'c' and 'f' and we ignored couple of charcters in between.
So, how do we find the longest common Subsequence? Yes, we will use Dynamic
Programming to solve this question.
So, here I have
on the first row, i have the first string
'a', 'b' ,'c', 'd', 'a', 'f'
and on the first column, i have the other string
'a', 'c', 'b', 'c' and 'f', second row and second column
are just populated with zeros, alright, so, now let's fill this matrix.
and finally, we'll have our solution when the matrix is totally filled.
So, when i'm filling this particular point
in the matrix, I'm asking myself if i had a
string "a" and "a" and nothing else, whatever will be the longest common subsequence here
so, the length of the longest common subsequence here will be one
when i have just these two guys, so, one.
now, i have strings "ab" and "a".
So, if i have strings "ab" and "a",
What is the length of the longest common subsequence here? again of length one.
when i have strings "abc" and "a",
What is the length of the longest common subsequence here?
Again length one, one, one, and one.
so if we had string "abcdaf" on one side and
just "a" on the other side, the longest common subsequence there
will be "a". Now, we'll fill
for this third row.
which will now include 'c'.
So, here we'll have 'a' and 'c' on one side and "a" on other side.
so, you'll ask yourself if I had string "ac" and "a",
what is the longest common subsequence here?
again one. Where did we get this one from? From the top.
so what we're saying is, if these two guys
are not same, then the length of the longest common subsequence will be
max of either the guy at the top or
the guy in the left. In this case, this is one so, it becomes one.
We have string "ab" and "ac", What is the length of the longest common subsequence here?
since 'c' and 'b' are not same, the value
here will be either the max of this or this. So, in this case, it's again one.
Here, we have string
"abc" and "ac", now, 'c' and 'c' are same,
so, the length of longest common subsequence
will be one because 'c' and 'c' are same plus
whatever the best we did between "ab" and "a", so this one.
so, one plus one two, so, again if these two guys are same,
so the length of the longest common subsequence will be this
plus one and if they are not same, then the max of this or this.
Let's fill 'd' in the same way. So, since 'c' and 'd' are not same,
we get the value from here, so two, two and two.
Alright let's move here.
if you have strings "acb" and "a",
the length of the longest common subsequence will be one
the guy from here. For now,
'b' and 'b' are same. So, the length of the longest common subsequence will be
this guy, diagonaly cross guy plus one, so two.
again 'b' and 'c' are not same,
so, the length will be max of these two which is two. Here, these guys are not same, so
max of these two, which is two, two and two.
Alright, let's move to next row.
So, here, we've
'c' and 'a', and they're not same, so the value from the top
one. Here, 'c' and 'b' are not same
so value from, max of this or this, so, two.
'c' and 'c' are same, so,
we go diagonally across, so, two
plus one, three. Again, when these two guys are same,
we are saying is that we already know that these guys will cntribute one to the
longest common subsequence
and we'll see the best we can do without these two guys. So, that is "ab" and "acb",
for which the number is here, two so, two plus one three.
This here is not same, so max of this this, so three.
they're not same, three they're not same, so three.
Let's fill up the last row.
So, one, two, three.
three, three. Since these two guys are same,
so, the value will be three plus one four, so, this is the lenght of our,
this is the length of the Longest Common Subsequence between them.
now if you want to find what that actual subsequence is,
we'll do this. So, we will start from here
and we'll see where this four is coming from? So, this four is not coming from
these two guys.
So, it's got to be coming from here. So, we know that 'f' is in the answer.
so, we'll move here.
Three. Where is this three coming from?
this three is coming from here, so, we moved
one step here, Where is this three coming from? This three is coming from here.
so we move one here. Where is this three coming from?
This three is coming from here, so we moved diagonal and whenever we move diagonal, we
include that
character, 'c', where is this two coming from?
this two is coming from here
So, we'll include 'b'.
and where is this one coming from? Top and where is this one coming from? here.
So, we'll include 'a'. Alright, so this is the
final result, 'a', 'b', 'c' and 'f' is our Longest Common Subsequence.
and the length is four. How would the formula look like?
Let me quickly write the formula.
if input[i]
equal equal to
if input1[i] is equal equal to input2[j],
then,
T[i][j] is equal to T[i-1][j-1] plus one,
else,
T[i][j] = max(T[i-1][j], T[i][j-1])
If you want the full solution for this problem,
Go to my Github Link: github.com/mission-peace/interview/wiki
Thanks for watching this video.