1
00:00:00,300 --> 00:00:07,920
When you are presented with a coding interview question, it's always important to identify what algorithmic

2
00:00:07,920 --> 00:00:10,320
approach you could take to solve the question.

3
00:00:10,350 --> 00:00:17,790
Now, if you're given the LCS question, let's discuss how you could identify that this is a DP problem.

4
00:00:17,790 --> 00:00:18,870
Now over here.

5
00:00:18,870 --> 00:00:23,580
Notice that in the two strings that are given to you, you have choices.

6
00:00:23,580 --> 00:00:30,420
That is, you can compare and decide whether you want to include two characters in a subsequence that

7
00:00:30,420 --> 00:00:33,690
you're trying to form or in the common subsequence that you're considering.

8
00:00:33,690 --> 00:00:42,480
So choices are involved over here, and you're also asked to find an optimal solution, because in the

9
00:00:42,480 --> 00:00:47,670
LCS problem, you're asked to find the longest common subsequence.

10
00:00:47,670 --> 00:00:50,700
So it's an optimal solution that is asked of us.

11
00:00:50,700 --> 00:00:54,270
Now these are two hints that you can use to identify that.

12
00:00:54,270 --> 00:00:57,420
You can use dynamic programming to solve this question.

13
00:00:57,420 --> 00:01:03,330
Another thing to keep in mind when you're trying to solve this question is that if you're encountering

14
00:01:03,330 --> 00:01:10,020
this question for the first time, then do not try to directly come up with the tabulation or bottom

15
00:01:10,020 --> 00:01:12,450
up approach because it's very difficult.

16
00:01:12,450 --> 00:01:19,620
Rather, take it step by step first, write the recursive approach, then implement the top down or

17
00:01:19,620 --> 00:01:25,470
memoization approach, and then use the insights that you get from these two steps to come up with the

18
00:01:25,470 --> 00:01:27,300
bottom up or tabulation approach.

19
00:01:27,300 --> 00:01:31,740
And then finally you can come up with the space optimized tabulation approach.

20
00:01:31,740 --> 00:01:39,240
If you approach DP questions in this manner, you will be able to master dynamic programming, and it

21
00:01:39,240 --> 00:01:46,020
will also help you successfully tackle new questions or questions that you have not previously seen.

22
00:01:46,020 --> 00:01:51,570
Let's now get started with the recursive approach for solving the LCS question.

23
00:01:51,570 --> 00:01:58,260
Now, because we are dealing with recursion, we will be dealing with choices and having a choice diagram

24
00:01:58,260 --> 00:02:01,800
is very helpful to visualize the choices at hand.

25
00:02:01,800 --> 00:02:07,740
And we will also be thinking of the base case because every recursive solution has a base case.

26
00:02:07,920 --> 00:02:13,080
Now let's take an example to come up with these two for the LCS question.

27
00:02:13,080 --> 00:02:18,540
So let's say you're given two strings a, b, c, d, e f and a c e f.

28
00:02:18,540 --> 00:02:25,710
So the LCS over here is four because notice over here a c, e f is the longest common subsequence.

29
00:02:25,710 --> 00:02:32,340
Now remember we have many times discussed that when you are writing a recursive solution you can either

30
00:02:32,370 --> 00:02:35,370
go from zero to n or n to zero.

31
00:02:35,370 --> 00:02:38,490
Now over here let's go from zero to n.

32
00:02:38,490 --> 00:02:45,930
Now to understand the choices involved, let's think of three possible scenarios.

33
00:02:45,930 --> 00:02:53,250
And let's try to think of what subproblem will have to take for finding the answer to the original solution

34
00:02:53,250 --> 00:02:55,140
in these three scenarios.

35
00:02:55,140 --> 00:03:02,970
So in the first scenario, let's say a, b, c, d, e, f and a c e f are the two strings.

36
00:03:02,970 --> 00:03:06,720
So again we're going from zero to n over here.

37
00:03:06,720 --> 00:03:15,030
So initially we would be comparing the characters at the zeroth index in these two strings.

38
00:03:15,030 --> 00:03:17,550
And notice that they are equal.

39
00:03:17,790 --> 00:03:19,710
So this is a possibility.

40
00:03:19,710 --> 00:03:25,290
Now if these are equal then we can definitely include this in our subsequence.

41
00:03:25,290 --> 00:03:34,080
And the subproblem which we would then need to recursively handle would be these two strings, where

42
00:03:34,080 --> 00:03:37,350
you're removing the first character from both the strings.

43
00:03:37,800 --> 00:03:42,090
Now in the second case, think of these two strings.

44
00:03:42,090 --> 00:03:46,680
Let's say you're given a, b, c, d, e f and r a b c.

45
00:03:46,920 --> 00:03:54,450
Notice that the characters at the zeroth index in these two strings are not equal.

46
00:03:55,610 --> 00:04:02,960
But that does not mean that we can directly consider this as the sub problem to be considered without

47
00:04:02,960 --> 00:04:03,830
adding anything.

48
00:04:03,830 --> 00:04:10,730
No, that cannot be done because notice that this a and this a over here, these are equal.

49
00:04:10,730 --> 00:04:16,850
So the sub problem over here that we need to consider would probably be this part over here.

50
00:04:17,060 --> 00:04:18,290
Let me draw it again.

51
00:04:18,290 --> 00:04:21,770
So the sub problem would be probably something like this.

52
00:04:22,160 --> 00:04:28,370
Now let's think of another possible scenario where you are given a, B, C, D, E and BCP.

53
00:04:28,580 --> 00:04:33,230
Again, the characters at the zeroth index are not equal.

54
00:04:33,230 --> 00:04:39,890
And notice that we cannot consider this as the next sub problem to be considered, because you have

55
00:04:39,890 --> 00:04:42,830
a B over here and you have a B over here.

56
00:04:43,580 --> 00:04:49,400
So probably the subproblem that we need to consider over here is this part over here.

57
00:04:49,850 --> 00:04:52,730
So broadly there are two possibilities.

58
00:04:52,730 --> 00:04:59,180
If the characters that we are comparing are equal, then the subproblem is what remains.

59
00:04:59,180 --> 00:05:05,360
But if the characters that we initially are comparing are not equal, then we would need to consider

60
00:05:05,360 --> 00:05:07,070
these two possibilities.

61
00:05:07,070 --> 00:05:14,930
And we have to find the maximum of the length of the subsequences that we get from these two approaches.

62
00:05:14,960 --> 00:05:17,210
Now what are these two approaches over here.

63
00:05:17,210 --> 00:05:19,460
Notice we did not move this index.

64
00:05:19,460 --> 00:05:22,940
But this index was moved forward to get the subproblem.

65
00:05:22,940 --> 00:05:25,400
And over here we did not move this index.

66
00:05:25,400 --> 00:05:28,760
This one was not moved but this index was moved forward.

67
00:05:28,760 --> 00:05:33,890
So basically only one index is moved and the other is kept constant.

68
00:05:33,920 --> 00:05:39,410
Now let's go ahead and draw the choice diagram based on what we have learned over here.

69
00:05:40,960 --> 00:05:44,440
So let's say these are the two strings that are given to us.

70
00:05:44,440 --> 00:05:47,770
And again the color just indicates the characters.

71
00:05:47,770 --> 00:05:48,970
So this is index zero.

72
00:05:48,970 --> 00:05:49,930
This is index one.

73
00:05:49,930 --> 00:05:51,310
This is index two.

74
00:05:51,340 --> 00:05:58,780
Now when we initially compare the characters at index zero this one and this one, there are two possibilities.

75
00:05:58,780 --> 00:06:01,870
The first possibility is that these two are equal.

76
00:06:01,870 --> 00:06:05,680
And the second possibility is that these two are not equal.

77
00:06:05,680 --> 00:06:12,160
Now, if these two are equal, then the subproblem becomes what is left over here, which is this part

78
00:06:12,160 --> 00:06:12,730
over here.

79
00:06:12,730 --> 00:06:19,750
And the answer would be one plus the length of the longest common subsequence in this subproblem.

80
00:06:20,080 --> 00:06:26,740
But if these two are not equal, then we would have two possibilities.

81
00:06:26,740 --> 00:06:30,610
The two subproblems to be considered are this one.

82
00:06:30,610 --> 00:06:31,330
Over here.

83
00:06:32,200 --> 00:06:34,150
And this one over here.

84
00:06:34,730 --> 00:06:39,890
Notice that over here for this sub problem we did not move this index.

85
00:06:39,890 --> 00:06:41,210
We kept it as it is.

86
00:06:41,210 --> 00:06:43,970
And we moved this index to the next index.

87
00:06:43,970 --> 00:06:47,030
And in this case we kept this one as it is.

88
00:06:47,030 --> 00:06:49,640
And we just moved this one to over here.

89
00:06:49,640 --> 00:06:53,120
So these two problems need to be evaluated.

90
00:06:53,120 --> 00:06:57,980
And we need to get the longest common subsequence from these two sub problems.

91
00:06:57,980 --> 00:07:04,040
And the maximum among these two has to be returned to find the answer to the original problem.

92
00:07:04,040 --> 00:07:10,400
So this gives us the choice diagram that we have to use to come up with the recursive case when we are

93
00:07:10,400 --> 00:07:12,410
implementing the recursion function.

94
00:07:12,950 --> 00:07:19,550
Now that we have the choice diagram, which we will use to implement the recursive case when we write

95
00:07:19,550 --> 00:07:24,740
the recursion function, let's also think of the base condition for this solution.

96
00:07:25,290 --> 00:07:32,130
Now, let's say that the length of the first string which is given to us is n, and let's say the length

97
00:07:32,130 --> 00:07:35,100
of the second string which is given to us is m.

98
00:07:35,680 --> 00:07:44,260
We would be hitting the base case when we encounter the last valid or the first invalid input.

99
00:07:44,290 --> 00:07:46,030
We have discussed that many times.

100
00:07:46,060 --> 00:07:54,010
Also, do remember that the base case will differ if you are going from zero to n or n to zero.

101
00:07:54,040 --> 00:07:57,880
Now over here we have decided to go from zero to N.

102
00:07:57,910 --> 00:08:03,040
Now if this is the approach that we take, then the base case would occur.

103
00:08:03,040 --> 00:08:09,580
When you come over here, for example, let's say we're using a variable I to iterate over these characters.

104
00:08:09,580 --> 00:08:11,650
So initially I is equal to zero.

105
00:08:11,650 --> 00:08:18,340
And then we keep incrementing I till I becomes this over here comes over here which is greater than

106
00:08:18,340 --> 00:08:21,520
the last index which would be n minus one.

107
00:08:21,670 --> 00:08:22,150
Right.

108
00:08:22,150 --> 00:08:27,550
And similarly in the case of j let's use j for iterating over these characters.

109
00:08:27,550 --> 00:08:29,290
So j would initially be zero.

110
00:08:29,290 --> 00:08:36,400
But then when j comes over here which is greater than m minus one, which is the last valid index,

111
00:08:36,400 --> 00:08:40,450
we would encounter the first invalid input over here as well.

112
00:08:40,450 --> 00:08:49,210
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

113
00:08:49,210 --> 00:08:56,350
one, then we have hit the base case, and in that case we can just return zero because it would mean

114
00:08:56,350 --> 00:08:59,290
that one of these strings has finished.

115
00:08:59,290 --> 00:09:05,740
And then there is no possibility to find any common characters between nothing and whatever is left

116
00:09:05,740 --> 00:09:06,970
in the other string.

117
00:09:06,970 --> 00:09:08,380
Now, what do I mean with that?

118
00:09:08,380 --> 00:09:09,640
Let's take an example.

119
00:09:09,640 --> 00:09:15,490
Let's say at a point we reach either I or J is beyond what is there.

120
00:09:15,490 --> 00:09:19,210
So we had values still over here, but then we have come over here.

121
00:09:19,210 --> 00:09:24,070
So we have hit an invalid input which indicates that this string is empty.

122
00:09:24,070 --> 00:09:27,940
And over here in this string let's say there are still characters left.

123
00:09:27,940 --> 00:09:35,110
So if we are comparing and trying to find the longest common subsequence between an empty string and

124
00:09:35,110 --> 00:09:37,990
a string that has characters, it would be zero.

125
00:09:37,990 --> 00:09:41,290
So that's why over here we can just return zero.

126
00:09:41,290 --> 00:09:44,800
And this is the base case for the recursive approach.

127
00:09:44,800 --> 00:09:51,340
So we have discussed the choice diagram and the base case for the recursive approach for solving the

128
00:09:51,340 --> 00:09:52,360
LCS question.

129
00:09:52,360 --> 00:09:57,910
In the next video, let's go ahead and write the pseudocode of the approach that we have discussed.