1
00:00:00,140 --> 00:00:01,160
Welcome back.

2
00:00:01,160 --> 00:00:04,370
Now let's discuss how we can solve this question.

3
00:00:04,370 --> 00:00:11,120
As you may have felt, this question is pretty similar to the palindromic substrings question that we

4
00:00:11,120 --> 00:00:12,230
have previously discussed.

5
00:00:12,230 --> 00:00:19,250
But before we go ahead and discuss the complete approach, first let's try to think how this question

6
00:00:19,250 --> 00:00:25,760
is different, or in what manners we would need to tweak the approach that we came up with for the palindromic

7
00:00:25,760 --> 00:00:31,310
substrings question, so that we can relate to that question, and then we can easily solve this question

8
00:00:31,310 --> 00:00:34,010
as well as retain what we are learning over here.

9
00:00:34,310 --> 00:00:40,250
Now, we could first try the recursive approach and then memorize it and then come to the tabulation

10
00:00:40,250 --> 00:00:41,870
approach for solving this question.

11
00:00:41,870 --> 00:00:48,380
But because we are already aware of this pattern, let's start with the tabulation approach right away

12
00:00:48,380 --> 00:00:48,770
okay.

13
00:00:48,770 --> 00:00:50,120
So let's get started.

14
00:00:50,120 --> 00:00:57,740
Now in the palindromic substrings question, this was the DP table that we had for the string p q p

15
00:00:57,740 --> 00:00:58,490
r p s.

16
00:00:58,490 --> 00:01:03,530
So if this is the string given to us, this is how we went ahead and formed a DP table.

17
00:01:03,530 --> 00:01:08,330
And then we iterated lengthwise and fill these values with either true or false.

18
00:01:08,330 --> 00:01:10,160
And we solved that question okay.

19
00:01:10,160 --> 00:01:17,780
So in the palindromic substrings question we filled either true or false in each of these cells.

20
00:01:17,780 --> 00:01:24,200
But in this question we will not be able to solve it by just filling the cells with true or false,

21
00:01:24,200 --> 00:01:30,110
especially because we are asked to identify the length of the longest palindromic subsequence.

22
00:01:30,110 --> 00:01:37,460
So what we would need to do is we would need to fill each cell with the longest palindromic subsequence

23
00:01:37,460 --> 00:01:44,270
that can be formed for the substring which is represented by a particular cell.

24
00:01:44,270 --> 00:01:44,780
Okay.

25
00:01:44,780 --> 00:01:47,960
Now let's go ahead and see how we can solve this question.

26
00:01:47,960 --> 00:01:54,200
And for this, or to form the intuition required for solving this question before we go ahead and iterate

27
00:01:54,200 --> 00:01:59,930
over the cells in the table and solve it, let's take a few examples to make a few observations.

28
00:01:59,930 --> 00:02:04,940
So if the string which is given to us where a b c b d a.

29
00:02:05,150 --> 00:02:10,250
Now in this case we would see that this a and this a is equal.

30
00:02:10,250 --> 00:02:13,490
So the first and the last characters are equal.

31
00:02:13,490 --> 00:02:22,340
And if these two are equal, then the longest palindromic subsequence that we can form from this complete

32
00:02:22,340 --> 00:02:27,620
string would be two, because we have one character over here and one character over here.

33
00:02:27,620 --> 00:02:33,110
And again these would be included in the longest palindromic subsequence that we can form from this

34
00:02:33,110 --> 00:02:33,590
string.

35
00:02:33,590 --> 00:02:35,570
So again these two will be included.

36
00:02:35,570 --> 00:02:41,720
So that's why the length of the longest palindromic subsequence that we can form from this string would

37
00:02:41,720 --> 00:02:49,220
be two plus the length of the longest palindromic subsequence that we can get from this substring.

38
00:02:49,220 --> 00:02:49,610
Okay.

39
00:02:49,610 --> 00:02:52,280
And again I'm just denoting this as l.

40
00:02:52,280 --> 00:02:54,650
So if this is L okay.

41
00:02:54,650 --> 00:03:01,310
Then the length of the longest palindromic subsequence that we can form from this string over here would

42
00:03:01,310 --> 00:03:03,320
be two plus l okay.

43
00:03:03,320 --> 00:03:05,150
And again why is this two over here.

44
00:03:05,150 --> 00:03:08,540
Because we have one character over here and one character over here.

45
00:03:08,540 --> 00:03:12,110
So l notice is being increased by two.

46
00:03:12,110 --> 00:03:12,560
Okay.

47
00:03:12,560 --> 00:03:14,570
Now let's take another example.

48
00:03:14,570 --> 00:03:18,530
If the string which we are dealing with is b c b d.

49
00:03:18,530 --> 00:03:20,570
And again that's this string over here.

50
00:03:20,570 --> 00:03:26,390
So if this is the string that we are dealing with we would see that the first and the last characters

51
00:03:26,390 --> 00:03:28,130
are not equal.

52
00:03:28,130 --> 00:03:35,720
And if that is the case then the longest palindromic subsequence that we are going to form from this

53
00:03:35,720 --> 00:03:41,360
string will either not include this character or not include this character.

54
00:03:41,360 --> 00:03:45,410
So what we will do is we will move only one pointer at a time.

55
00:03:45,410 --> 00:03:49,400
So when we move this pointer we get b c b okay.

56
00:03:49,400 --> 00:03:52,790
We are moving this pointer to over here and we'll get BCB.

57
00:03:52,790 --> 00:03:56,540
And if we move this pointer we will get CBD okay.

58
00:03:56,540 --> 00:04:03,920
And then we will try to find the longest palindromic subsequence that we can form in these two scenarios.

59
00:04:03,920 --> 00:04:05,510
So we'll get two numbers.

60
00:04:05,510 --> 00:04:12,620
And then we will take the maximum of these two as the longest palindromic subsequence that we can form

61
00:04:12,620 --> 00:04:15,080
from this string over here okay.

62
00:04:15,080 --> 00:04:21,530
And in this case we can see that for this substring we can form a palindromic subsequence of length

63
00:04:21,530 --> 00:04:21,980
three.

64
00:04:21,980 --> 00:04:26,720
And in this case we are just able to form a palindromic subsequence of length one.

65
00:04:26,720 --> 00:04:30,380
So the greater value between these two is going to be equal to three.

66
00:04:30,380 --> 00:04:36,860
So for this string we will be able to form a palindromic subsequence of length three.

67
00:04:36,860 --> 00:04:42,710
And then the answer for this complete string would be three plus two which is equal to five.

68
00:04:42,710 --> 00:04:46,130
So this is the approach that we will use to solve this question.

69
00:04:46,130 --> 00:04:53,510
Now again remember we will fill each cell in the DP table with the length of the longest palindromic

70
00:04:53,510 --> 00:04:59,270
subsequence that can be formed from the substring which the cell represents okay.

71
00:04:59,270 --> 00:04:59,630
So for.

72
00:04:59,850 --> 00:05:07,080
Example, this cell over here represents the substring that starts at index one and goes up to index

73
00:05:07,080 --> 00:05:07,500
four.

74
00:05:07,500 --> 00:05:10,170
So that's q p r p okay.

75
00:05:10,170 --> 00:05:11,610
So that's q p r p.

76
00:05:11,610 --> 00:05:18,360
And over here in this cell we will fill the length of the longest palindromic subsequence that can be

77
00:05:18,360 --> 00:05:22,590
formed from this substring over here which would be three which is p r p.

78
00:05:22,590 --> 00:05:22,890
Okay.

79
00:05:22,890 --> 00:05:27,870
So we have understood the approach that we will be taking to solve this question.

80
00:05:27,870 --> 00:05:33,750
Now again one more point to remember at this point when we are trying to find the length of the longest

81
00:05:33,750 --> 00:05:41,280
palindromic subsequence that we can form from this string, notice it's being reduced to two subproblems

82
00:05:41,280 --> 00:05:46,830
which are of lower length, so the length of this substring is equal to four, and the length of these

83
00:05:46,830 --> 00:05:49,890
two substrings are three and three respectively.

84
00:05:49,890 --> 00:05:55,860
And because we are going to iterate over these cells in the DP table over here, length wise, we would

85
00:05:55,860 --> 00:05:58,740
already have the answers to these two problems.

86
00:05:58,740 --> 00:06:04,770
So that's why we can use the answers to the previous subproblems, which we would have already computed

87
00:06:04,770 --> 00:06:08,040
to find the answer for this problem over here.

88
00:06:08,040 --> 00:06:08,490
Okay.

89
00:06:08,490 --> 00:06:12,000
And that's the beauty of length wise iteration.

90
00:06:12,000 --> 00:06:15,360
So let's go ahead and see how this pans out.

91
00:06:15,360 --> 00:06:18,270
And let's just do a dry run of the algorithm.

92
00:06:18,270 --> 00:06:23,010
Now we are taking the string which is given to us as p q p r p s.

93
00:06:23,040 --> 00:06:23,520
Okay.

94
00:06:23,520 --> 00:06:29,700
So first we're going to iterate over these cells which represent length equal to one.

95
00:06:29,700 --> 00:06:33,780
So at this point we would see that the two characters are equal okay.

96
00:06:33,780 --> 00:06:36,360
And we are just dealing with substrings of length one.

97
00:06:36,360 --> 00:06:39,420
So we would just fill one in each of these cases.

98
00:06:39,420 --> 00:06:40,740
Now why is that the case.

99
00:06:40,740 --> 00:06:46,650
That's because for example this cell over here represents the substring that starts at index two and

100
00:06:46,650 --> 00:06:48,960
goes up to index two which is just p.

101
00:06:48,960 --> 00:06:55,170
And if you have a string of length one, the character itself is a palindrome and the length is just

102
00:06:55,170 --> 00:06:55,380
one.

103
00:06:55,380 --> 00:06:55,620
Okay.

104
00:06:55,620 --> 00:06:57,120
So that's why we fill one over here.

105
00:06:57,120 --> 00:07:03,240
Now we move to this diagonal over here, which represents substrings of length two.

106
00:07:03,240 --> 00:07:11,970
Now if we are analyzing a substring of length two, we would either fill two in the cell or one right.

107
00:07:12,330 --> 00:07:13,500
Again why is that the case?

108
00:07:13,500 --> 00:07:15,570
If you are having a substring that looks like this.

109
00:07:15,570 --> 00:07:19,410
For example b b, we see that this itself is a palindrome.

110
00:07:19,410 --> 00:07:25,590
And therefore we would say that the longest palindromic subsequence that can be formed from this substring

111
00:07:25,590 --> 00:07:26,790
has a length of two.

112
00:07:26,790 --> 00:07:32,550
Now, if you are dealing with a substring that looks like this, for example, which is b a, we see

113
00:07:32,550 --> 00:07:38,760
that these two are not equal, but we can still form a palindromic subsequence of length one, which

114
00:07:38,760 --> 00:07:41,100
is either b or a alone.

115
00:07:41,100 --> 00:07:46,680
Okay, so that's why we would either have 1 or 2 filled in these cells over here.

116
00:07:46,680 --> 00:07:48,660
Now let's see how it pans out.

117
00:07:48,660 --> 00:07:52,080
So for this cell we see that we have p and q.

118
00:07:52,080 --> 00:07:53,670
So these two are not equal.

119
00:07:53,670 --> 00:07:55,620
So we are going to fill one over here.

120
00:07:55,710 --> 00:07:58,740
And in this cell we have q and p.

121
00:07:58,740 --> 00:07:59,640
They are not equal.

122
00:07:59,640 --> 00:08:00,840
So we'll have one again.

123
00:08:00,840 --> 00:08:02,760
Then we have p and we have r.

124
00:08:02,760 --> 00:08:03,750
They are not equal.

125
00:08:03,750 --> 00:08:05,670
So we have one over here as well.

126
00:08:05,670 --> 00:08:09,420
Then we have r and we have p and they are not equal.

127
00:08:09,420 --> 00:08:11,550
Therefore we have one over here as well.

128
00:08:11,550 --> 00:08:14,520
And over here we have p and over here we have s.

129
00:08:14,520 --> 00:08:16,620
So these two are also not equal.

130
00:08:16,620 --> 00:08:17,850
And therefore we have one.

131
00:08:17,850 --> 00:08:21,390
So all of these cells for the given string have the value one.

132
00:08:21,390 --> 00:08:28,290
Now we proceed to the next diagonal which is this diagonal over here which represents strings of length

133
00:08:28,290 --> 00:08:28,800
three.

134
00:08:28,800 --> 00:08:37,320
Now when we are dealing with a string of length three, if these two characters are equal, then the

135
00:08:37,320 --> 00:08:43,320
longest palindromic subsequence that we can form using this string would be two plus one.

136
00:08:43,320 --> 00:08:47,610
Okay, because this is a palindrome because it's just one character.

137
00:08:47,610 --> 00:08:54,720
Now, if these two characters are not equal, then we would have to consider this substring and this

138
00:08:54,720 --> 00:08:58,110
substring separately and identify the larger value.

139
00:08:58,110 --> 00:08:58,440
Okay.

140
00:08:58,440 --> 00:09:05,310
So if length is equal to three either we will get the longest palindromic subsequence length as three.

141
00:09:05,310 --> 00:09:11,370
If the first and last characters are equal, and if the first and last characters are not equal, then

142
00:09:11,370 --> 00:09:17,370
we have to find the maximum between the length of the longest palindromic subsequence that we can form.

143
00:09:17,370 --> 00:09:24,120
Considering this substring versus this substring over here okay, so let's go ahead and see how this

144
00:09:24,120 --> 00:09:24,780
works out.

145
00:09:24,780 --> 00:09:28,830
So over here for this cell we see that we have p and p.

146
00:09:28,830 --> 00:09:29,970
They are equal.

147
00:09:29,970 --> 00:09:32,730
Therefore we are going to apply this logic.

148
00:09:32,730 --> 00:09:36,000
And that's just doing two plus one okay.

149
00:09:36,000 --> 00:09:37,470
Again why is this the case.

150
00:09:37,470 --> 00:09:39,810
Now let me just note down this over here.

151
00:09:39,810 --> 00:09:44,250
So if we say that this cell is depee at I j.

152
00:09:45,870 --> 00:09:52,590
Then, because the first and last characters for the string that we are considering are equal, I can

153
00:09:52,590 --> 00:10:01,050
say that this is equal to two plus depee at I plus one j minus one.

154
00:10:01,050 --> 00:10:06,720
Okay, so this is what we get when we remove or not consider the first and last characters.

155
00:10:06,720 --> 00:10:08,550
And over here that's what we are seeing okay.

156
00:10:08,550 --> 00:10:15,270
So in this case DP at I plus one J minus one is this cell over here which just represents Q.

157
00:10:15,270 --> 00:10:16,590
And that's what we get right.

158
00:10:16,590 --> 00:10:18,600
If you have p, q and p.

159
00:10:18,600 --> 00:10:22,620
And if you are removing the first and last characters, you're just left with q.

160
00:10:22,620 --> 00:10:27,840
So DP at I, j is equal to two plus dp at I plus one j minus one.

161
00:10:27,840 --> 00:10:29,580
So that's how we get three over here.

162
00:10:29,580 --> 00:10:34,740
And proceeding further over here we see we have Q and R and they are not equal.

163
00:10:34,740 --> 00:10:39,510
So we have to identify the maximum between this case and this case.

164
00:10:39,510 --> 00:10:46,020
Now notice that in the DP table this case over here is represented by this cell.

165
00:10:46,700 --> 00:10:51,560
Okay where it starts at Q and goes up to P instead of R.

166
00:10:51,590 --> 00:10:52,070
Right.

167
00:10:52,070 --> 00:10:53,450
So that's q p.

168
00:10:53,450 --> 00:11:01,100
And this case over here is represented by this cell over here where it starts at P and goes up to R

169
00:11:01,100 --> 00:11:02,750
which is this substring okay.

170
00:11:02,750 --> 00:11:09,380
So we have q p r and this is q p and this is p r.

171
00:11:09,380 --> 00:11:14,480
And notice that q p is this cell and p r is this cell.

172
00:11:14,480 --> 00:11:20,870
And because these are of lower length than the length of q p r we have already computed them because

173
00:11:20,870 --> 00:11:22,400
we are iterating length wise.

174
00:11:22,400 --> 00:11:29,690
So this cell over here is going to take the maximum value between this value and this value.

175
00:11:29,690 --> 00:11:32,360
Now for this example over here we have one.

176
00:11:32,360 --> 00:11:33,950
And over here we have one.

177
00:11:33,950 --> 00:11:37,250
And the maximum between 1 and 1 is just one.

178
00:11:37,250 --> 00:11:39,680
And therefore we will fill one over here.

179
00:11:40,010 --> 00:11:41,030
Let's proceed.

180
00:11:41,030 --> 00:11:45,140
Now we come to this cell over here and we see that we have P over here.

181
00:11:45,140 --> 00:11:46,550
And we have P over here.

182
00:11:46,550 --> 00:11:48,020
And they are equal right.

183
00:11:48,020 --> 00:11:49,880
So we are dealing with p r p.

184
00:11:49,880 --> 00:11:52,250
That's the substring that we are dealing with.

185
00:11:52,250 --> 00:11:54,140
And p is equal to p.

186
00:11:54,170 --> 00:12:00,500
Therefore the value that we are going to fill over here is two plus this value over here which is equal

187
00:12:00,500 --> 00:12:01,160
to three.

188
00:12:02,170 --> 00:12:02,830
Okay.

189
00:12:02,830 --> 00:12:05,440
And that's the same thing that we discussed over here as well.

190
00:12:05,710 --> 00:12:09,730
Now we proceed to the next cell, which is this cell over here.

191
00:12:09,730 --> 00:12:13,330
And we see that we have are over here and we have s over here.

192
00:12:13,330 --> 00:12:18,100
So we are dealing with r p s and r is not equal to s.

193
00:12:18,100 --> 00:12:25,150
And therefore this cell over here will take the maximum value between this cell and this cell.

194
00:12:25,150 --> 00:12:27,370
Now over here and here we have one.

195
00:12:27,370 --> 00:12:30,640
So the maximum between these two values is one itself.

196
00:12:30,640 --> 00:12:33,040
And that's why we fill one over here.

197
00:12:33,040 --> 00:12:37,120
So that's how we were able to fill these cells.

198
00:12:37,120 --> 00:12:41,020
Now we proceed to the next diagonal and we come over here.

199
00:12:41,020 --> 00:12:43,960
We see we have P over here and we have R over here.

200
00:12:43,960 --> 00:12:45,190
They are not equal.

201
00:12:45,190 --> 00:12:51,040
Therefore this cell will take the maximum value between what we have over here and what we have over

202
00:12:51,040 --> 00:12:51,310
here.

203
00:12:51,310 --> 00:12:51,640
Okay.

204
00:12:51,640 --> 00:12:53,200
So that's this case over here.

205
00:12:53,200 --> 00:12:56,200
Now the maximum between 3 and 1 is three.

206
00:12:56,200 --> 00:12:58,090
So we will fill three over here.

207
00:12:58,090 --> 00:13:01,570
And then when we come to this cell we have Q over here.

208
00:13:01,570 --> 00:13:02,590
And P over here.

209
00:13:02,590 --> 00:13:03,700
They are not equal.

210
00:13:03,700 --> 00:13:08,110
So this cell will take the maximum between 1 and 3.

211
00:13:08,110 --> 00:13:10,510
And the greater between these two values is three.

212
00:13:10,510 --> 00:13:16,600
So we'll fill three over here and over here also we see that we have p and s.

213
00:13:16,600 --> 00:13:17,920
They are not equal.

214
00:13:17,920 --> 00:13:22,060
Therefore we take the maximum between 3 and 1 which is equal to three.

215
00:13:22,060 --> 00:13:23,620
And hence we fill three.

216
00:13:23,620 --> 00:13:26,230
Over here we proceed to the next diagonal.

217
00:13:26,230 --> 00:13:28,270
So we have p and p okay.

218
00:13:28,270 --> 00:13:35,020
So they are equal now because they are equal we'll just take two plus whatever we have over here.

219
00:13:35,020 --> 00:13:36,550
And over here we have one.

220
00:13:36,550 --> 00:13:38,680
So two plus one is equal to three.

221
00:13:38,680 --> 00:13:40,630
And therefore we will fill three over here.

222
00:13:40,630 --> 00:13:42,370
And again notice this works.

223
00:13:42,370 --> 00:13:48,340
So again this cell over here represents the case where we are starting at index zero and going up to

224
00:13:48,340 --> 00:13:49,060
index four.

225
00:13:49,060 --> 00:13:54,700
So that's this substring which is p q p r p okay.

226
00:13:54,700 --> 00:14:03,640
Now notice that the longest palindromic subsequence that you can form is p p p and p has a length of

227
00:14:03,640 --> 00:14:03,910
three.

228
00:14:03,910 --> 00:14:06,310
And that's what you're getting over here okay.

229
00:14:06,310 --> 00:14:10,780
Now we proceed to this cell and we have Q over here and S over here.

230
00:14:10,780 --> 00:14:14,980
So we are dealing with this substring q p r p s.

231
00:14:14,980 --> 00:14:17,740
And we see that q is not equal to s.

232
00:14:17,740 --> 00:14:23,200
Therefore this cell will take the greater value between this value and this value.

233
00:14:23,200 --> 00:14:25,000
And we have three and three over here.

234
00:14:25,000 --> 00:14:30,160
So whatever we are going to fill over here is the maximum between these two which is three itself.

235
00:14:31,140 --> 00:14:31,800
All right.

236
00:14:31,830 --> 00:14:38,580
Now we come to the last cell over here, and at this point we have P and S, and they are not equal.

237
00:14:38,580 --> 00:14:43,230
Therefore, this cell will take the maximum between this value and this value.

238
00:14:43,230 --> 00:14:45,540
And that would be three itself okay.

239
00:14:45,540 --> 00:14:46,860
So we fill three over here.

240
00:14:46,860 --> 00:14:49,470
And this gives us the answer right.

241
00:14:49,470 --> 00:14:57,330
Again notice this cell represents the longest palindromic subsequence length that we can form where

242
00:14:57,330 --> 00:15:04,260
the substring involved starts at index zero and goes up to index five, which is in fact the problem

243
00:15:04,260 --> 00:15:05,370
that is given to us.

244
00:15:05,370 --> 00:15:10,350
So that's why once we are able to fill this cell, we'll just need to return this.

245
00:15:10,350 --> 00:15:12,090
And this will be the answer.

246
00:15:12,090 --> 00:15:20,250
And again notice in this depee table this cell would be depee at zero at n minus one okay.

247
00:15:20,250 --> 00:15:21,750
So this is the zeroth row.

248
00:15:21,750 --> 00:15:25,860
And this would be the n minus one column with respect to indexing.

249
00:15:25,860 --> 00:15:26,130
Right.

250
00:15:26,130 --> 00:15:31,080
Because the indexing starts at zero and goes up to n minus one for n columns.

251
00:15:31,080 --> 00:15:35,910
So again at the end we'll just need to return depee at zero n minus one.

252
00:15:35,910 --> 00:15:37,980
And this will give us the answer.

253
00:15:37,980 --> 00:15:44,190
So this is how we will solve the longest palindromic subsequence question using the tabulation approach.