When you are presented with a coding interview question, it's always important to identify what algorithmic
approach you could take to solve the question.
Now, if you're given the LCS question, let's discuss how you could identify that this is a DP problem.
Now over here.
Notice that in the two strings that are given to you, you have choices.
That is, you can compare and decide whether you want to include two characters in a subsequence that
you're trying to form or in the common subsequence that you're considering.
So choices are involved over here, and you're also asked to find an optimal solution, because in the
LCS problem, you're asked to find the longest common subsequence.
So it's an optimal solution that is asked of us.
Now these are two hints that you can use to identify that.
You can use dynamic programming to solve this question.
Another thing to keep in mind when you're trying to solve this question is that if you're encountering
this question for the first time, then do not try to directly come up with the tabulation or bottom
up approach because it's very difficult.
Rather, take it step by step first, write the recursive approach, then implement the top down or
memoization approach, and then use the insights that you get from these two steps to come up with the
bottom up or tabulation approach.
And then finally you can come up with the space optimized tabulation approach.
If you approach DP questions in this manner, you will be able to master dynamic programming, and it
will also help you successfully tackle new questions or questions that you have not previously seen.
Let's now get started with the recursive approach for solving the LCS question.
Now, because we are dealing with recursion, we will be dealing with choices and having a choice diagram
is very helpful to visualize the choices at hand.
And we will also be thinking of the base case because every recursive solution has a base case.
Now let's take an example to come up with these two for the LCS question.
So let's say you're given two strings a, b, c, d, e f and a c e f.
So the LCS over here is four because notice over here a c, e f is the longest common subsequence.
Now remember we have many times discussed that when you are writing a recursive solution you can either
go from zero to n or n to zero.
Now over here let's go from zero to n.
Now to understand the choices involved, let's think of three possible scenarios.
And let's try to think of what subproblem will have to take for finding the answer to the original solution
in these three scenarios.
So in the first scenario, let's say a, b, c, d, e, f and a c e f are the two strings.
So again we're going from zero to n over here.
So initially we would be comparing the characters at the zeroth index in these two strings.
And notice that they are equal.
So this is a possibility.
Now if these are equal then we can definitely include this in our subsequence.
And the subproblem which we would then need to recursively handle would be these two strings, where
you're removing the first character from both the strings.
Now in the second case, think of these two strings.
Let's say you're given a, b, c, d, e f and r a b c.
Notice that the characters at the zeroth index in these two strings are not equal.
But that does not mean that we can directly consider this as the sub problem to be considered without
adding anything.
No, that cannot be done because notice that this a and this a over here, these are equal.
So the sub problem over here that we need to consider would probably be this part over here.
Let me draw it again.
So the sub problem would be probably something like this.
Now let's think of another possible scenario where you are given a, B, C, D, E and BCP.
Again, the characters at the zeroth index are not equal.
And notice that we cannot consider this as the next sub problem to be considered, because you have
a B over here and you have a B over here.
So probably the subproblem that we need to consider over here is this part over here.
So broadly there are two possibilities.
If the characters that we are comparing are equal, then the subproblem is what remains.
But if the characters that we initially are comparing are not equal, then we would need to consider
these two possibilities.
And we have to find the maximum of the length of the subsequences that we get from these two approaches.
Now what are these two approaches over here.
Notice we did not move this index.
But this index was moved forward to get the subproblem.
And over here we did not move this index.
This one was not moved but this index was moved forward.
So basically only one index is moved and the other is kept constant.
Now let's go ahead and draw the choice diagram based on what we have learned over here.
So let's say these are the two strings that are given to us.
And again the color just indicates the characters.
So this is index zero.
This is index one.
This is index two.
Now when we initially compare the characters at index zero this one and this one, there are two possibilities.
The first possibility is that these two are equal.
And the second possibility is that these two are not equal.
Now, if these two are equal, then the subproblem becomes what is left over here, which is this part
over here.
And the answer would be one plus the length of the longest common subsequence in this subproblem.
But if these two are not equal, then we would have two possibilities.
The two subproblems to be considered are this one.
Over here.
And this one over here.
Notice that over here for this sub problem we did not move this index.
We kept it as it is.
And we moved this index to the next index.
And in this case we kept this one as it is.
And we just moved this one to over here.
So these two problems need to be evaluated.
And we need to get the longest common subsequence from these two sub problems.
And the maximum among these two has to be returned to find the answer to the original problem.
So this gives us the choice diagram that we have to use to come up with the recursive case when we are
implementing the recursion function.
Now that we have the choice diagram, which we will use to implement the recursive case when we write
the recursion function, let's also think of the base condition for this solution.
Now, let's say that the length of the first string which is given to us is n, and let's say the length
of the second string which is given to us is m.
We would be hitting the base case when we encounter the last valid or the first invalid input.
We have discussed that many times.
Also, do remember that the base case will differ if you are going from zero to n or n to zero.
Now over here we have decided to go from zero to N.
Now if this is the approach that we take, then the base case would occur.
When you come over here, for example, let's say we're using a variable I to iterate over these characters.
So initially I is equal to zero.
And then we keep incrementing I till I becomes this over here comes over here which is greater than
the last index which would be n minus one.
Right.
And similarly in the case of j let's use j for iterating over these characters.
So j would initially be zero.
But then when j comes over here which is greater than m minus one, which is the last valid index,
we would encounter the first invalid input over here as well.
So we can say that the base case is if I is greater than n minus one, or if j is greater than m minus
one, then we have hit the base case, and in that case we can just return zero because it would mean
that one of these strings has finished.
And then there is no possibility to find any common characters between nothing and whatever is left
in the other string.
Now, what do I mean with that?
Let's take an example.
Let's say at a point we reach either I or J is beyond what is there.
So we had values still over here, but then we have come over here.
So we have hit an invalid input which indicates that this string is empty.
And over here in this string let's say there are still characters left.
So if we are comparing and trying to find the longest common subsequence between an empty string and
a string that has characters, it would be zero.
So that's why over here we can just return zero.
And this is the base case for the recursive approach.
So we have discussed the choice diagram and the base case for the recursive approach for solving the
LCS question.
In the next video, let's go ahead and write the pseudocode of the approach that we have discussed.