1
00:00:00,460 --> 00:00:01,540
Welcome back.

2
00:00:01,540 --> 00:00:09,580
So far we have discussed the recursive approach and the memoization approach for solving the LCS question.

3
00:00:09,580 --> 00:00:16,330
For the memoization approach, we have seen that the space and time complexity were of the order of

4
00:00:16,330 --> 00:00:24,130
n into M, and this is still recursive in nature, so we do use space on the recursive call stack.

5
00:00:24,130 --> 00:00:28,420
Notice that the time complexity has significantly improved.

6
00:00:28,420 --> 00:00:35,260
It was over here of the order of two to the power n plus m, but over here the time complexity is of

7
00:00:35,260 --> 00:00:37,240
the order of n into m.

8
00:00:37,240 --> 00:00:43,660
Now the space complexity over here was better, but then the improvement in time complexity makes it

9
00:00:43,660 --> 00:00:44,230
worth.

10
00:00:44,230 --> 00:00:51,670
Now let's proceed and discuss the tabulation or bottom up approach, which is iterative in nature for

11
00:00:51,670 --> 00:00:53,350
solving the LCS question.

12
00:00:54,110 --> 00:00:54,890
For this.

13
00:00:54,890 --> 00:00:56,330
Let's take an example.

14
00:00:56,330 --> 00:01:02,300
Let's say the two strings which are given to us are p q, r s t and p r t.

15
00:01:02,570 --> 00:01:10,250
Now the length of this string is five and the length of this string is equal to three.

16
00:01:10,280 --> 00:01:14,150
Now if we add one to both over here we have six.

17
00:01:14,150 --> 00:01:15,860
And over here we have four.

18
00:01:15,890 --> 00:01:27,140
So for the bottom up or tabulation approach when we create a DP table we would need six rows and four

19
00:01:27,140 --> 00:01:28,850
columns or vice versa.

20
00:01:28,880 --> 00:01:29,360
All right.

21
00:01:29,360 --> 00:01:31,250
So over here let's draw that.

22
00:01:31,250 --> 00:01:34,850
So notice that we have p r t over here.

23
00:01:34,850 --> 00:01:38,660
And we have an extra column over here which is empty in nature.

24
00:01:38,660 --> 00:01:41,840
And we have rows for p q r s t.

25
00:01:41,840 --> 00:01:45,440
But we have an extra row over here for an empty string.

26
00:01:45,440 --> 00:01:49,670
Now in the memoization approach we did not need this.

27
00:01:49,670 --> 00:01:53,120
But in the tabulation approach this is quite handy.

28
00:01:53,120 --> 00:01:59,300
And it's a common practice to have something like this when we come up with the table for tabulation.

29
00:01:59,300 --> 00:02:07,160
Now this is useful because we will use values from the previous row for identifying the value in a current

30
00:02:07,160 --> 00:02:07,850
cell.

31
00:02:08,360 --> 00:02:11,540
Let's say we want to identify the value that goes over here.

32
00:02:11,540 --> 00:02:17,900
And for this we would use something from the previous row values and probably from a previous cell.

33
00:02:17,900 --> 00:02:25,370
So that's why it's handy to have this, because we can just use this to fill out the initial conditions.

34
00:02:25,370 --> 00:02:31,280
Now before that, let's quickly take a moment to understand what each cell represents.

35
00:02:31,280 --> 00:02:36,200
Now for example, what is the subproblem represented by this cell over here?

36
00:02:36,200 --> 00:02:45,260
Now the subproblem represented by this is p q having one string as p q and the other string as p r.

37
00:02:45,290 --> 00:02:48,500
Because over here we just have characters till q.

38
00:02:48,500 --> 00:02:50,690
So this becomes p q.

39
00:02:50,690 --> 00:02:52,910
And over here we have characters till r.

40
00:02:52,910 --> 00:02:54,950
So this string becomes p r.

41
00:02:54,950 --> 00:02:56,870
So that's this subproblem over here.

42
00:02:58,100 --> 00:03:02,750
Now let's go ahead and fill the initial conditions with zero.

43
00:03:02,750 --> 00:03:05,810
So we have zero over here and we have zero over here.

44
00:03:05,810 --> 00:03:08,030
Now you can think of it in two ways.

45
00:03:08,030 --> 00:03:14,060
Remember we have discussed when we were discussing the recursive approach that when we were coming to

46
00:03:14,060 --> 00:03:21,710
an index which was not part of these strings, then we would not be able to find any common characters,

47
00:03:21,710 --> 00:03:26,720
and therefore the length of the common subsequence in that case would be just zero.

48
00:03:26,720 --> 00:03:29,990
So that's why we have zero over here and zero over here.

49
00:03:29,990 --> 00:03:30,980
Because think of it.

50
00:03:30,980 --> 00:03:32,900
What does this row represent?

51
00:03:32,900 --> 00:03:35,030
For example, what is this subproblem?

52
00:03:35,030 --> 00:03:41,840
This subproblem is having an empty string as one string and PR as the other string.

53
00:03:41,840 --> 00:03:43,730
So that's this subproblem over here.

54
00:03:43,730 --> 00:03:50,510
And if one string is empty and the other string is PR, then the length of the common subsequence of

55
00:03:50,510 --> 00:03:53,390
the longest common subsequence would be just zero.

56
00:03:53,390 --> 00:03:57,260
So that's why this complete row can be filled with zero.

57
00:03:57,260 --> 00:04:01,280
And in a similar manner, let's say this subproblem over here.

58
00:04:01,280 --> 00:04:06,920
This means one string is empty and the other string is p q r.

59
00:04:07,490 --> 00:04:14,120
Now if one is p q r and the other string is empty, there are no common characters, and therefore the

60
00:04:14,120 --> 00:04:16,490
LCS for this subproblem is zero.

61
00:04:16,490 --> 00:04:20,120
And that's why we can fill this complete row with zero.

62
00:04:20,570 --> 00:04:24,860
So we have discussed the initial conditions over here we have everything zero.

63
00:04:24,860 --> 00:04:27,290
And over here we have everything zero.

64
00:04:27,290 --> 00:04:34,670
Now let's discuss how we can iterate over each cell that remains in this table to find the answer to

65
00:04:34,670 --> 00:04:35,720
the problem at hand.

66
00:04:35,720 --> 00:04:38,810
So we first start with this cell.

67
00:04:38,810 --> 00:04:44,960
And remember from the implementation of the recursive approach, we have discussed when we drew the

68
00:04:44,960 --> 00:04:47,780
choice diagram that there are two possibilities.

69
00:04:47,780 --> 00:04:49,970
The two possibilities are one.

70
00:04:49,970 --> 00:04:55,160
The two characters that we are comparing are equal, and the other possibility is that the characters

71
00:04:55,160 --> 00:04:58,130
that we are comparing are not equal.

72
00:04:58,650 --> 00:05:05,520
Now, if the characters that we are considering are equal, then previously what we discussed was we

73
00:05:05,520 --> 00:05:08,580
would just do one plus a recursive call.

74
00:05:08,580 --> 00:05:13,770
So the equivalent of it in this table would be depee at ij.

75
00:05:13,920 --> 00:05:19,050
And let's say the indices I and j are used to iterate over these two strings.

76
00:05:19,050 --> 00:05:24,360
And let's say we find that the characters at these two indices are equal.

77
00:05:24,360 --> 00:05:33,720
Now if that is the case, then dp at ij would be equal to one plus dp at I minus one and j minus one.

78
00:05:33,720 --> 00:05:35,310
Now what does this mean?

79
00:05:35,310 --> 00:05:42,630
Let's for example, take this example over here where the subproblems are p q r and p r.

80
00:05:42,630 --> 00:05:44,370
So we have p q r.

81
00:05:45,550 --> 00:05:46,930
And we have PR.

82
00:05:46,960 --> 00:05:50,410
Now we see that these two characters are equal.

83
00:05:50,440 --> 00:05:50,860
All right.

84
00:05:50,860 --> 00:05:52,420
So these two are equal.

85
00:05:53,070 --> 00:06:00,690
Now, because these two are equal, we would just need to do one plus the solution to the sub problem

86
00:06:00,690 --> 00:06:04,560
where the strings are p, q and p.

87
00:06:04,590 --> 00:06:14,220
Now what is the place in the DP table where we have this sub problem which is p q and that's this p

88
00:06:14,220 --> 00:06:14,640
q.

89
00:06:15,740 --> 00:06:16,790
And P.

90
00:06:16,790 --> 00:06:18,260
That's this P over here.

91
00:06:18,260 --> 00:06:20,450
So the intersection is over here.

92
00:06:21,970 --> 00:06:27,190
Which is nothing but d p I minus one and j minus one.

93
00:06:27,190 --> 00:06:27,700
All right.

94
00:06:27,700 --> 00:06:35,650
So that's why when the characters are found to be equal, depee at I j would just be one plus dp at

95
00:06:35,650 --> 00:06:37,780
I minus one j minus one.

96
00:06:37,960 --> 00:06:44,290
Now let's use this to fill the table over here because notice that p and p are equal.

97
00:06:44,290 --> 00:06:47,440
So we have a case where the characters are equal.

98
00:06:47,440 --> 00:06:53,410
So dp at I minus one j minus one is nothing but the diagonal element.

99
00:06:54,550 --> 00:07:01,240
And we would just have to take this value and add one to it, because we have filled the initial conditions

100
00:07:01,240 --> 00:07:01,780
over here.

101
00:07:01,780 --> 00:07:08,470
Notice that we already have this value, and we can just add one to this value to get one.

102
00:07:08,470 --> 00:07:10,000
And we can fill one over here.

103
00:07:10,420 --> 00:07:13,150
Now let's proceed to the next cell.

104
00:07:13,150 --> 00:07:17,800
So over here we see that we have P over here and we have R over here.

105
00:07:17,800 --> 00:07:19,750
And these are not equal.

106
00:07:19,750 --> 00:07:26,320
Now in the implementation the recursive implementation we have discussed in the choice diagram that

107
00:07:26,320 --> 00:07:32,770
when the characters that we are comparing are not equal, we would have to do two recursive calls and

108
00:07:32,770 --> 00:07:35,500
we would only increment one index at a time.

109
00:07:35,500 --> 00:07:39,460
And then we would have to find the maximum between those two values.

110
00:07:39,460 --> 00:07:43,270
So what would be the equivalent of it in the tabulation approach.

111
00:07:43,270 --> 00:07:52,540
So we can say that we would have to find the maximum between depee at I minus one j and dp at I j minus

112
00:07:52,540 --> 00:07:52,870
one.

113
00:07:52,870 --> 00:07:53,770
Now why is that?

114
00:07:53,770 --> 00:07:55,390
So let's take this example.

115
00:07:55,390 --> 00:07:59,200
So we have PR over here and we just have P over here.

116
00:07:59,200 --> 00:08:00,970
That's this subproblem over here.

117
00:08:00,970 --> 00:08:04,330
So we have PR and we have p.

118
00:08:04,600 --> 00:08:08,740
Now we see that these two characters are not equal.

119
00:08:08,740 --> 00:08:14,110
Now because these two are not equal we will have to take two possibilities.

120
00:08:14,110 --> 00:08:17,740
One possibility is where we take p and p.

121
00:08:18,070 --> 00:08:21,070
We change this index to from R to p.

122
00:08:21,070 --> 00:08:26,020
And the other possibility let me write that over here is taking R.

123
00:08:26,680 --> 00:08:33,520
And nothing because we moved this index, we kept this there itself and we moved this index.

124
00:08:33,520 --> 00:08:36,700
So again notice over here we had p r and p.

125
00:08:37,540 --> 00:08:40,690
So these are the two indices that are being considered.

126
00:08:40,690 --> 00:08:44,230
So in one case I'm moving this this index to over here.

127
00:08:44,230 --> 00:08:47,320
So that's this case where I'm getting p and p.

128
00:08:47,320 --> 00:08:50,590
And the other case I'm leaving this over here itself.

129
00:08:50,590 --> 00:08:52,240
So I have it here itself.

130
00:08:52,240 --> 00:08:55,030
And I'm moving this index to this place over here.

131
00:08:55,030 --> 00:08:56,830
So I'm getting R and nothing.

132
00:08:56,830 --> 00:08:58,870
So these are the two possibilities.

133
00:08:58,870 --> 00:09:02,470
So I need to find the answer to these two subproblems.

134
00:09:02,470 --> 00:09:05,740
And I need to take the maximum between these two.

135
00:09:05,740 --> 00:09:09,400
So what are these two subproblems in the DP table.

136
00:09:09,400 --> 00:09:13,390
So having r or p r this is R right.

137
00:09:13,390 --> 00:09:17,230
When you have are you still have p r and you have nothing over here.

138
00:09:17,230 --> 00:09:18,820
So p r and nothing.

139
00:09:18,820 --> 00:09:22,450
So that's having p r over here and nothing over here.

140
00:09:22,450 --> 00:09:23,920
Which is this over here.

141
00:09:24,610 --> 00:09:25,120
Right.

142
00:09:25,120 --> 00:09:26,260
So that's top.

143
00:09:26,900 --> 00:09:30,470
Or you can think of it as DP at I minus one J.

144
00:09:30,680 --> 00:09:35,990
And this one over here having p and p that's this p over here.

145
00:09:35,990 --> 00:09:37,160
And this p over here.

146
00:09:37,160 --> 00:09:43,040
That's this cell over here which is the left cell or DP at I j minus one.

147
00:09:43,040 --> 00:09:50,390
So basically we have seen that when the two characters that we are comparing are not equal, we need

148
00:09:50,390 --> 00:09:55,310
to find depee at I minus one j and dp at I j minus one.

149
00:09:55,310 --> 00:09:58,430
And that's the top cell and the left cell.

150
00:09:58,430 --> 00:10:02,780
And between these two we just need to find which is the greater value.

151
00:10:02,780 --> 00:10:07,790
And that would be the value that we can fill in the cell at hand which is dp at ij.

152
00:10:07,910 --> 00:10:13,070
So over here between 0 and 1 the maximum value or the greater value is one.

153
00:10:13,070 --> 00:10:14,990
So we can fill over here one.

154
00:10:15,680 --> 00:10:16,760
Again we proceed.

155
00:10:16,760 --> 00:10:22,640
Now we are comparing p and t and notice that these are not equal.

156
00:10:22,640 --> 00:10:28,430
Therefore we just need to take the maximum between the top value and the left value.

157
00:10:28,430 --> 00:10:31,460
So between 0 and 1 the greater value is one.

158
00:10:31,460 --> 00:10:34,940
So we fill one over here and we are done with this row.

159
00:10:34,940 --> 00:10:36,680
Now we come over here.

160
00:10:36,680 --> 00:10:40,580
And for this cell we have Q over here and P over here.

161
00:10:40,580 --> 00:10:42,020
These are not equal.

162
00:10:42,020 --> 00:10:46,340
So we take the maximum between 0 and 1 which is equal to one.

163
00:10:46,340 --> 00:10:50,060
And in a similar manner over here we have q and r.

164
00:10:50,090 --> 00:10:51,470
Again they are not equal.

165
00:10:51,470 --> 00:10:55,850
So between 1 and 1 the maximum value is one itself.

166
00:10:55,850 --> 00:10:57,410
So we fill one over here.

167
00:10:57,410 --> 00:11:02,960
And then when we have q and we have t we again see these are not equal.

168
00:11:02,960 --> 00:11:04,640
So the left value is one.

169
00:11:04,640 --> 00:11:05,900
The top value is one.

170
00:11:05,900 --> 00:11:08,720
So the maximum between 1 and 1 is one itself.

171
00:11:08,720 --> 00:11:10,550
And we can fill one over here.

172
00:11:10,550 --> 00:11:13,010
So we are done with this row as well.

173
00:11:13,010 --> 00:11:14,480
And we come over here.

174
00:11:14,480 --> 00:11:17,390
Now we have R and over here we have p.

175
00:11:17,420 --> 00:11:18,890
These are not equal.

176
00:11:18,890 --> 00:11:22,070
So between 0 and 1 the greater value is one.

177
00:11:22,070 --> 00:11:23,750
So we can fill one over here.

178
00:11:23,750 --> 00:11:25,670
Now we come to this cell.

179
00:11:25,670 --> 00:11:29,600
So we have R again over here and over here also we have r.

180
00:11:29,630 --> 00:11:31,250
Now these are equal.

181
00:11:31,250 --> 00:11:37,490
So therefore we come to the diagonal value which is dp at I minus one j minus one.

182
00:11:37,490 --> 00:11:39,110
And we add one to it.

183
00:11:39,110 --> 00:11:42,770
So one plus one gives us two which is this value over here.

184
00:11:42,770 --> 00:11:46,250
Then we come to the next cell we have r and we have t.

185
00:11:46,280 --> 00:11:47,720
These are not equal.

186
00:11:47,720 --> 00:11:50,300
So we take the left and the top cell.

187
00:11:50,300 --> 00:11:51,650
So we have two and one.

188
00:11:51,650 --> 00:11:53,690
And the maximum between these two is two.

189
00:11:53,720 --> 00:11:55,400
So we can fill two over here.

190
00:11:56,100 --> 00:11:57,270
We're done with this row.

191
00:11:57,270 --> 00:11:58,800
Now, let's come to this cell.

192
00:11:58,800 --> 00:11:59,370
Over here.

193
00:11:59,370 --> 00:12:00,510
We have S and P.

194
00:12:00,510 --> 00:12:01,890
They are not equal.

195
00:12:01,890 --> 00:12:05,640
So between 0 and 1 the greater value is one.

196
00:12:05,640 --> 00:12:06,960
So we fill that over here.

197
00:12:06,960 --> 00:12:10,740
And again over here we are comparing s and r.

198
00:12:10,740 --> 00:12:12,120
So they are not equal.

199
00:12:12,120 --> 00:12:16,050
So between zero and between 1 and 2 two is the greater value.

200
00:12:16,050 --> 00:12:17,340
So we fill two over here.

201
00:12:17,340 --> 00:12:19,320
And then we come to the next cell.

202
00:12:19,320 --> 00:12:20,760
So we have s and t.

203
00:12:20,760 --> 00:12:21,930
They are not equal.

204
00:12:21,930 --> 00:12:27,900
So between 2 and 2 again the maximum value is two itself which can be filled over here.

205
00:12:27,900 --> 00:12:29,490
And we are done with this row.

206
00:12:29,490 --> 00:12:32,610
And we come over here we have T and P.

207
00:12:32,610 --> 00:12:33,690
They are not equal.

208
00:12:33,690 --> 00:12:36,660
So between 0 and 1 the greater value is one.

209
00:12:36,660 --> 00:12:37,830
We fill that over here.

210
00:12:37,830 --> 00:12:41,610
And then we have t and r and they are not equal.

211
00:12:41,610 --> 00:12:44,430
So between 1 and 2 the greater value is two.

212
00:12:44,460 --> 00:12:45,870
So we fill that over here.

213
00:12:45,870 --> 00:12:47,310
And then we have t and t.

214
00:12:48,030 --> 00:12:49,680
Now t and t are equal.

215
00:12:49,680 --> 00:12:52,110
So we take the diagonal value which is two.

216
00:12:52,110 --> 00:12:54,720
And we add one to it to get three.

217
00:12:54,720 --> 00:12:56,700
And we fill three over here.

218
00:12:56,700 --> 00:13:00,240
And this is the answer to the problem at hand.

219
00:13:00,240 --> 00:13:02,640
So the answer to this question is three.

220
00:13:02,640 --> 00:13:04,320
Now why is this the answer.

221
00:13:04,320 --> 00:13:11,520
Because notice that this cell represents the problem where you have p q r s t and p r t.

222
00:13:11,520 --> 00:13:13,800
And that's the question which was given to us.

223
00:13:13,800 --> 00:13:18,390
So that's why whatever we get over here is the answer to the problem.

224
00:13:18,390 --> 00:13:25,320
And this is the tabulation approach or the bottom up approach which we can take to solve the LCS question.