1
00:00:00,630 --> 00:00:05,730
Let's now do a dry run for the approach that we have discussed in the previous video.

2
00:00:05,730 --> 00:00:10,290
So let's again take the input string as a b, a, a, c.

3
00:00:10,290 --> 00:00:15,690
And we have already discussed that this is going to be our DP table which is a 2D array.

4
00:00:15,690 --> 00:00:22,410
And we have a, b, a, a, c on the columns as well as over here we have a, b, a, C on the rows.

5
00:00:22,410 --> 00:00:28,380
And the indices over here range from zero up to four, which is true for columns and rows.

6
00:00:28,410 --> 00:00:34,680
Now we are going to start iterating over the substrings in a length wise manner.

7
00:00:35,480 --> 00:00:41,960
So we have these cells over here which all represent strings of length one.

8
00:00:41,960 --> 00:00:47,120
And we know that if a string just has one character, these are palindromes.

9
00:00:47,120 --> 00:00:50,480
And because they are palindromes, we will not require any cut.

10
00:00:50,480 --> 00:00:55,610
So we can fill these values over here with zero which represents zero cuts.

11
00:00:56,240 --> 00:01:03,290
Now we proceed to this cell over here, which represents the substring that starts at index zero and

12
00:01:03,290 --> 00:01:05,630
goes up to index one, which is a b.

13
00:01:05,780 --> 00:01:12,020
Now for a b, because a and b are not equal, we will need one cut.

14
00:01:12,020 --> 00:01:15,920
So that's why we can fill the value over here with one.

15
00:01:16,710 --> 00:01:23,490
Now we proceed to this cell, which represents the substring that starts at index one and goes up to

16
00:01:23,490 --> 00:01:25,980
index two, which is b again.

17
00:01:26,010 --> 00:01:27,750
B is not equal to a.

18
00:01:27,750 --> 00:01:31,920
Therefore we would need to do one cut and we can fill one over here.

19
00:01:31,920 --> 00:01:37,140
And then we come to this cell again it starts at index two and goes up to index three.

20
00:01:37,140 --> 00:01:38,340
That's AA.

21
00:01:38,370 --> 00:01:40,980
Now we see that A and A are equal.

22
00:01:40,980 --> 00:01:42,780
These two characters are equal.

23
00:01:42,780 --> 00:01:44,670
And therefore this is a palindrome.

24
00:01:44,670 --> 00:01:46,860
And we do not need any cuts.

25
00:01:46,860 --> 00:01:49,290
And therefore we can fill zero over here.

26
00:01:49,290 --> 00:01:51,510
Then we proceed to this cell over here.

27
00:01:51,510 --> 00:01:58,140
It represents the substring that starts at index three and goes till index four which is A-C.

28
00:01:58,290 --> 00:02:00,240
Now a and c are not equal.

29
00:02:00,240 --> 00:02:02,190
And therefore we will need one cut.

30
00:02:02,190 --> 00:02:03,960
And we can fill one over here.

31
00:02:03,960 --> 00:02:06,090
And we are done with this diagonal.

32
00:02:06,090 --> 00:02:08,460
Now we proceed to these cells over here.

33
00:02:08,460 --> 00:02:15,390
So this cell over here represents the substring that starts at index zero and goes up to index two which

34
00:02:15,390 --> 00:02:16,290
is ABBA.

35
00:02:17,060 --> 00:02:25,160
Now we see that these two are equal, A and A is equal, and the remaining part of ABA after we remove

36
00:02:25,190 --> 00:02:27,590
A and a is also a palindrome.

37
00:02:27,590 --> 00:02:29,630
So over here also we have a palindrome.

38
00:02:29,630 --> 00:02:35,900
Therefore for ABA we will need no cuts because ABA is a palindrome in itself.

39
00:02:35,900 --> 00:02:37,850
So we can fill zero over here.

40
00:02:37,850 --> 00:02:40,310
Now let's proceed to the next cell.

41
00:02:40,310 --> 00:02:47,360
So over here we have the substring that starts at index one and goes up to index three, which is b,

42
00:02:47,360 --> 00:02:51,200
a, a and b and a are not equal.

43
00:02:51,200 --> 00:02:55,280
So let's think of the two steps that we have discussed in the previous video.

44
00:02:55,280 --> 00:02:59,270
First we will have to decide about making one cut.

45
00:02:59,270 --> 00:03:02,360
And then we would have to analyze the subproblems.

46
00:03:02,360 --> 00:03:06,290
So what are the ways in which we can make one cut over here.

47
00:03:06,290 --> 00:03:11,780
So again these are the indices 123 in the string which is given to us.

48
00:03:11,780 --> 00:03:13,610
So b is index one.

49
00:03:13,610 --> 00:03:17,240
This is index two which is a and index three also has an a.

50
00:03:17,270 --> 00:03:20,540
So what are the different ways in which we can make one cut.

51
00:03:20,540 --> 00:03:24,470
So we can have b and a a or B a and a.

52
00:03:24,560 --> 00:03:33,380
Now b over here just b is represented by the substring that starts at index one and goes up to index

53
00:03:33,380 --> 00:03:33,650
one.

54
00:03:33,650 --> 00:03:37,370
So this over here can be represented as one comma one.

55
00:03:37,370 --> 00:03:43,550
And this substring over here is the substring that starts at index two and goes up to index three.

56
00:03:43,550 --> 00:03:45,830
So we can write two comma three over here.

57
00:03:45,830 --> 00:03:48,620
And in a similar manner b a over here.

58
00:03:48,620 --> 00:03:52,160
This starts at index one and goes up to index two.

59
00:03:52,160 --> 00:03:57,080
And this substring over here starts at index three and goes up to index three.

60
00:03:57,080 --> 00:04:02,930
As we have discussed in the previous video, this over here is achieved using one more variable.

61
00:04:02,930 --> 00:04:04,610
So let's call that k.

62
00:04:04,610 --> 00:04:07,550
So over here k has the value one.

63
00:04:07,550 --> 00:04:09,860
And over here k has the value two.

64
00:04:09,860 --> 00:04:13,040
So k ranges from one up to two right.

65
00:04:13,040 --> 00:04:15,170
So from I up to j minus one.

66
00:04:15,170 --> 00:04:17,600
So over here k has the value one.

67
00:04:17,600 --> 00:04:19,850
And over here k has the value two.

68
00:04:19,850 --> 00:04:26,870
And in each of these cases we have to calculate the number of cuts required for these two subproblems

69
00:04:26,870 --> 00:04:28,640
and add one to it.

70
00:04:28,640 --> 00:04:36,320
Because this in fact is a cut which is dividing the problem at hand, which is b a into these two subproblems

71
00:04:36,320 --> 00:04:38,420
in these two ways.

72
00:04:38,540 --> 00:04:43,550
So let's go ahead and take a look at the number of cuts required in these two scenarios.

73
00:04:43,550 --> 00:04:49,520
So over here we have B and this is a palindrome because it has just one character.

74
00:04:49,520 --> 00:04:53,150
So we just need zero cuts for this string over here.

75
00:04:53,150 --> 00:04:56,900
And for this string a because this is a palindrome.

76
00:04:56,900 --> 00:04:59,060
Again we would just need zero cuts.

77
00:04:59,060 --> 00:05:03,080
Therefore DP at I k over here is zero and dp at k plus one.

78
00:05:03,080 --> 00:05:09,290
J is also equal to zero, and the total number of cuts required is zero plus one plus zero.

79
00:05:09,740 --> 00:05:11,720
Now what about this case over here.

80
00:05:11,720 --> 00:05:20,180
Now BA this subproblem over here will require one cut to divide this into two palindromes b and a.

81
00:05:20,180 --> 00:05:22,310
So we will need one cut over here.

82
00:05:22,310 --> 00:05:27,590
And then because this is just one character this substring over here is a palindrome.

83
00:05:27,590 --> 00:05:29,570
So we would need zero cuts over here.

84
00:05:29,570 --> 00:05:34,310
So the total cuts required would be one plus one plus zero.

85
00:05:34,310 --> 00:05:37,070
Because dp at I k in this case is one.

86
00:05:37,070 --> 00:05:38,990
And then we have this one over here.

87
00:05:39,260 --> 00:05:43,010
And then dp at k plus one j in this case is equal to zero.

88
00:05:43,010 --> 00:05:47,060
So we have seen the number of cuts required in these two cases.

89
00:05:47,060 --> 00:05:51,440
Let's also take a look at these values in the DP table that we have.

90
00:05:51,440 --> 00:05:57,080
Now we know that we have already solved problems which are of lower length than three.

91
00:05:57,080 --> 00:05:59,060
So the length of this problem is three.

92
00:05:59,060 --> 00:06:04,100
So we already have the solutions to problems of length one and length two.

93
00:06:04,100 --> 00:06:07,010
And that's the case of these subproblems over here.

94
00:06:07,010 --> 00:06:15,260
So over here this substring which starts at index one and ends at index one is in fact this cell over

95
00:06:15,260 --> 00:06:15,620
here.

96
00:06:15,620 --> 00:06:16,130
Right.

97
00:06:16,130 --> 00:06:18,980
It starts at index one and goes up to index one.

98
00:06:18,980 --> 00:06:22,460
And the value zero is something that we have already computed.

99
00:06:22,610 --> 00:06:28,340
Similarly this subproblem over here, which is the substring that starts at index two and goes till

100
00:06:28,340 --> 00:06:32,990
index three, is this subproblem which is represented by this cell.

101
00:06:32,990 --> 00:06:36,230
So it starts at index two and goes up to index three.

102
00:06:36,230 --> 00:06:40,070
And we already have the value zero which is something that we're using over here.

103
00:06:40,070 --> 00:06:41,750
So we have already calculated it.

104
00:06:41,750 --> 00:06:49,130
Similarly this subproblem which starts at index one and goes up to index two is this cell or represented

105
00:06:49,130 --> 00:06:49,940
by this cell.

106
00:06:49,940 --> 00:06:52,370
And we already have computed it previously.

107
00:06:52,370 --> 00:06:58,880
And this subproblem which starts at index three and goes up to index three is this cell or represented

108
00:06:58,880 --> 00:06:59,750
by this cell.

109
00:06:59,750 --> 00:07:03,020
And it has the value zero which is what we are using over here.

110
00:07:03,020 --> 00:07:09,380
So notice how we are using things that we have previously calculated to find the answer to the problem

111
00:07:09,380 --> 00:07:13,100
at hand, which is the minimum number of cuts required for BA.

112
00:07:13,310 --> 00:07:16,220
Now we know that there are these two possibilities.

113
00:07:16,220 --> 00:07:16,370
So.

114
00:07:16,490 --> 00:07:18,740
So in this case we would need one cut.

115
00:07:18,740 --> 00:07:21,350
And in this case we would need two cuts.

116
00:07:21,350 --> 00:07:24,560
And the minimum between these two is equal to one.

117
00:07:24,560 --> 00:07:27,860
And therefore the solution for this becomes one.

118
00:07:27,860 --> 00:07:29,210
And we can fill that over here.

119
00:07:29,210 --> 00:07:35,420
So the problem which starts at index one and goes up to index three, which is what we have over here

120
00:07:35,420 --> 00:07:37,640
can be solved with just one cut.

121
00:07:37,640 --> 00:07:39,140
So that's what we have found over here.

122
00:07:39,140 --> 00:07:41,810
And we feel that in this cell over here.

123
00:07:41,810 --> 00:07:44,060
Now let's proceed with the next cell.

124
00:07:44,060 --> 00:07:51,590
So over here we have the substring that starts at index two and goes up to index four which is a a c.

125
00:07:51,710 --> 00:07:54,440
Now again we see that a and c are not equal.

126
00:07:54,440 --> 00:07:57,290
Therefore let's think of making one cut.

127
00:07:57,290 --> 00:08:00,500
And the indices over here are two, three and four.

128
00:08:00,530 --> 00:08:07,460
Now the different ways in which we can do one cut are A and a, C and a and c.

129
00:08:07,490 --> 00:08:13,910
Now for this case we would not require any cut for a and for a C we would need one cut.

130
00:08:13,910 --> 00:08:17,750
So the total number of cuts required would be zero plus one plus one.

131
00:08:17,750 --> 00:08:20,540
And over here we do not need a cut for a.

132
00:08:20,570 --> 00:08:22,550
We also do not need a cut for C.

133
00:08:22,580 --> 00:08:25,730
So the total cuts would be zero plus one plus zero.

134
00:08:25,940 --> 00:08:27,980
So over here we need two cuts.

135
00:08:27,980 --> 00:08:29,840
And over here we need just one cut.

136
00:08:29,840 --> 00:08:32,930
And the minimum between these two is equal to one.

137
00:08:32,930 --> 00:08:35,600
And therefore we can fill one over here.

138
00:08:35,600 --> 00:08:37,490
And we are done with this diagonal.

139
00:08:37,490 --> 00:08:45,080
Now let's proceed to the next case which is the substring a b a a now a and a over here are equal.

140
00:08:45,080 --> 00:08:51,320
But when we consider the remaining substring, when we remove these two characters, we have ba, which

141
00:08:51,320 --> 00:08:52,730
is not a palindrome.

142
00:08:52,730 --> 00:08:58,160
Therefore, this substring over here is not a palindrome, and we proceed with our approach.

143
00:08:58,160 --> 00:09:00,560
First we think of making one cut.

144
00:09:00,590 --> 00:09:08,510
Now the different ways in which we can make a cut are a, b a a a, b, a, a, a, b, a, and a.

145
00:09:08,630 --> 00:09:14,180
Now in each of these cases, we will have to find the number of cuts that would be required for the

146
00:09:14,180 --> 00:09:14,810
substrings.

147
00:09:14,810 --> 00:09:18,350
And we already have computed them in the DP table over here.

148
00:09:18,350 --> 00:09:22,490
Because notice that the length of this substring is equal to four.

149
00:09:22,490 --> 00:09:25,970
But the length of the subproblems over here are less than four.

150
00:09:25,970 --> 00:09:31,190
And because we have been iterating lengthwise, we have already calculated these and we already know

151
00:09:31,190 --> 00:09:33,350
how to get these from the DP table.

152
00:09:33,350 --> 00:09:35,300
It's just dp at I k.

153
00:09:37,190 --> 00:09:45,860
That would give us these substrings or these subproblems, and then depee at k plus one J will give

154
00:09:45,860 --> 00:09:53,630
us these subproblems, and then the number of cuts required would be dp at I k plus one plus dp at k

155
00:09:53,630 --> 00:09:54,680
plus one j.

156
00:09:54,710 --> 00:10:00,650
Now let's go ahead and take a look at the number of cuts required for these three cases respectively.

157
00:10:00,650 --> 00:10:06,770
So over here we would need zero plus one plus one cuts because we have to do a cut over here.

158
00:10:06,770 --> 00:10:11,480
And in this case we would need one cut over here and zero cuts over here.

159
00:10:11,480 --> 00:10:12,560
And over here.

160
00:10:12,560 --> 00:10:14,000
We would need zero cuts.

161
00:10:14,000 --> 00:10:16,520
And over here also we would need zero cuts.

162
00:10:16,520 --> 00:10:18,200
So this is equal to two.

163
00:10:18,230 --> 00:10:19,280
This is equal to two.

164
00:10:19,280 --> 00:10:20,720
And this is equal to one.

165
00:10:20,720 --> 00:10:23,750
And the minimum between these three is equal to one.

166
00:10:23,750 --> 00:10:27,320
And that's why we can fill this cell over here with the value one.

167
00:10:27,650 --> 00:10:30,140
And then let's proceed to the next cell.

168
00:10:30,140 --> 00:10:34,640
The problem over here starts at index two and goes up to index four.

169
00:10:34,640 --> 00:10:37,250
That's the substring b a c.

170
00:10:37,280 --> 00:10:39,740
Now we see that b and c are not equal.

171
00:10:39,740 --> 00:10:42,860
Therefore we have to think of making one cut.

172
00:10:42,860 --> 00:10:50,900
Now the different ways in which this can be done is b a a c b a, a c and b a, a and c, and the indices

173
00:10:50,900 --> 00:10:53,300
over here are one, two, three and four.

174
00:10:53,300 --> 00:10:57,980
And let's take a look at the number of cuts that would be required in these three cases.

175
00:10:57,980 --> 00:11:00,200
So over here we need zero cuts.

176
00:11:00,200 --> 00:11:02,000
And over here we would need one cut.

177
00:11:02,000 --> 00:11:04,460
So that's zero plus one plus one.

178
00:11:04,460 --> 00:11:07,010
And in this case we would need one cut.

179
00:11:07,010 --> 00:11:09,350
And over here also we would need one cut.

180
00:11:09,350 --> 00:11:11,480
So that's one plus one plus one.

181
00:11:11,480 --> 00:11:14,660
And over here we would need one cut and zero cuts over here.

182
00:11:14,660 --> 00:11:17,330
So that's one plus one plus zero.

183
00:11:17,330 --> 00:11:21,440
So the minimum among these three is equal to two.

184
00:11:21,440 --> 00:11:24,680
And therefore we can fill two in this cell over here.

185
00:11:25,520 --> 00:11:26,630
So let's do that.

186
00:11:28,010 --> 00:11:32,630
And again in the table we find this using another variable called k.

187
00:11:32,660 --> 00:11:38,900
So this over here represents k is equal to one because k goes from I up to j minus one.

188
00:11:38,900 --> 00:11:39,860
So k is one.

189
00:11:39,860 --> 00:11:44,720
Is this scenario k is equal to two, is this scenario and k is equal to three is this scenario.

190
00:11:44,720 --> 00:11:50,570
And in each of these cases, the value for the number of cuts required for this sub problem would be

191
00:11:50,570 --> 00:11:57,200
given by dp at I k, and the value for the number of cuts required for these sub problems would be given

192
00:11:57,200 --> 00:11:59,450
by dp k plus one j.

193
00:11:59,450 --> 00:12:02,840
And then we're just going to find this for each of these cases.

194
00:12:02,840 --> 00:12:07,400
And then we will find the minimum among these and assign it to the cell at hand.

195
00:12:07,400 --> 00:12:09,620
So this is how we filled two over here.

196
00:12:10,040 --> 00:12:16,220
And the final problem starts at index zero and goes up to index four which is a b a a c.

197
00:12:16,220 --> 00:12:22,610
And this will give us the answer because a b, a c is the question that was asked of us.

198
00:12:22,610 --> 00:12:27,080
So we have a b a a c, we see that a and c are not equal.

199
00:12:27,080 --> 00:12:29,630
So we proceed and we will make one cut.

200
00:12:29,660 --> 00:12:38,840
Now the different ways of doing this are a, b a, a, c a b a, a c a b a a c and a b a, a and c,

201
00:12:39,080 --> 00:12:41,150
and over here k is equal to zero.

202
00:12:41,180 --> 00:12:42,230
We have k equal to one.

203
00:12:42,230 --> 00:12:46,040
Over here k is equal to two over here, and k is equal to three over here.

204
00:12:46,040 --> 00:12:53,840
And in each of these cases we are going to find depee at I k and dp at k plus one j dp at I k will give

205
00:12:53,840 --> 00:13:00,140
us the number of cuts required for these subproblems, and dp at k plus one j will give us the number

206
00:13:00,140 --> 00:13:02,480
of cuts required for these subproblems over here.

207
00:13:02,480 --> 00:13:09,560
So when k is equal to zero dp at I k and again I is equal to zero and j is equal to four.

208
00:13:09,560 --> 00:13:14,630
So dp at I, k is dp at zero zero, which is equal to zero.

209
00:13:14,630 --> 00:13:19,490
And again we know that for this substring we will just require zero cuts.

210
00:13:19,490 --> 00:13:25,580
And this value over here would be dp at one four because k is equal to zero.

211
00:13:25,580 --> 00:13:29,330
So this is dp at zero plus one which is one and j is four.

212
00:13:29,330 --> 00:13:30,890
So dp at one four.

213
00:13:31,690 --> 00:13:33,100
Is this value over here.

214
00:13:33,100 --> 00:13:35,980
So back will require two cuts.

215
00:13:35,980 --> 00:13:40,240
So the total number of cuts required would be zero plus one plus two.

216
00:13:40,420 --> 00:13:46,090
Similarly over here the number of cuts that would be required is one plus one plus one.

217
00:13:46,090 --> 00:13:49,120
And over here we have zero plus one plus one.

218
00:13:49,120 --> 00:13:53,080
And finally over here we have one plus one plus zero.

219
00:13:53,200 --> 00:13:58,180
And the minimum value among these four values is equal to two.

220
00:13:58,180 --> 00:14:01,840
And therefore we can fill two in the cell over here.

221
00:14:03,030 --> 00:14:05,490
And this is the answer to the question.

222
00:14:05,490 --> 00:14:12,720
So the minimum number of cuts required for a, b, a, a, c such that all the substrings are palindromes

223
00:14:12,720 --> 00:14:14,370
is equal to two.