1
00:00:00,560 --> 00:00:02,180
Hey there and welcome back.

2
00:00:02,360 --> 00:00:07,340
Let's now discuss the tabulation approach for solving palindrome partitioning two.

3
00:00:07,370 --> 00:00:09,920
Now we're going to discuss two approaches.

4
00:00:09,950 --> 00:00:14,180
Over here we'll discuss the approach where we are going to use a 2D DP array.

5
00:00:14,180 --> 00:00:20,660
But after this we will also discuss the approach where you can solve this by just using a one dimensional

6
00:00:20,660 --> 00:00:21,200
DP array.

7
00:00:21,230 --> 00:00:22,640
So let's get started.

8
00:00:22,670 --> 00:00:29,330
Now first let's spend some time and build the intuition which is necessary to solve this question.

9
00:00:29,360 --> 00:00:36,170
So again remember over here the question deals with substrings and not with subsequences.

10
00:00:36,170 --> 00:00:38,060
So this is an important thing to note.

11
00:00:38,090 --> 00:00:39,890
Now let's take an example.

12
00:00:39,890 --> 00:00:43,610
Let's say the string at hand is a b a b a.

13
00:00:44,000 --> 00:00:49,070
Now over here we see that the first and last characters are equal.

14
00:00:49,070 --> 00:00:53,990
And we also see that the middle part over here is a palindrome in itself.

15
00:00:53,990 --> 00:01:01,310
So therefore if this is the case, we can conclude that the string at hand which is a b a, b a, is

16
00:01:01,310 --> 00:01:08,240
a palindrome and therefore no cuts are required for a, b a, b, so zero cuts are required if this

17
00:01:08,240 --> 00:01:08,960
is a string.

18
00:01:09,440 --> 00:01:15,050
Another observation that we can make is that if the string that we are considering consists of only

19
00:01:15,050 --> 00:01:20,870
one character, then because this over here is a palindrome, we would need zero cuts.

20
00:01:21,860 --> 00:01:23,900
Now let's take another example.

21
00:01:23,900 --> 00:01:27,920
Let's say the string that we're considering is a, b a, a, c.

22
00:01:29,270 --> 00:01:33,170
Over here, we see that these two characters are not equal.

23
00:01:33,200 --> 00:01:39,710
Now, to identify the minimum cuts required for this problem, let's think of it in two steps.

24
00:01:39,710 --> 00:01:42,500
First we are going to make one cut.

25
00:01:42,500 --> 00:01:45,860
And then we are going to analyze the subproblems.

26
00:01:46,070 --> 00:01:48,350
Let's take some time to think about this.

27
00:01:48,350 --> 00:01:51,740
First let's discuss making one cut.

28
00:01:51,740 --> 00:01:54,770
Now the problem is a b a, c.

29
00:01:54,890 --> 00:02:02,900
And we are going to make one cut in a way that this string over here is divided into two sub strings

30
00:02:02,900 --> 00:02:06,110
or sub problems, where each sub string is a sub problem.

31
00:02:06,110 --> 00:02:09,050
Now what are the different ways in which we can do this.

32
00:02:09,050 --> 00:02:11,600
So I have a b a c over here.

33
00:02:11,810 --> 00:02:17,390
And I can either do the cut over here or over here over here over here.

34
00:02:17,390 --> 00:02:23,450
So depending on where I do the cut the two sub strings are a and b a c.

35
00:02:23,450 --> 00:02:30,200
If I do the cut over here a b and a c if I do the cut over here and in a similar manner, I could get

36
00:02:30,200 --> 00:02:33,980
a, b a and a c or a b, a, a and c.

37
00:02:34,130 --> 00:02:38,990
Now let me write the indices over here I have 01234.

38
00:02:38,990 --> 00:02:44,810
Notice that if I make the cut at index zero I am getting this scenario over here.

39
00:02:44,810 --> 00:02:51,470
If I make the cut at index one, then I'm getting this scenario over here where I have a B over here

40
00:02:51,470 --> 00:02:53,330
and a C over here.

41
00:02:53,330 --> 00:02:58,430
Similarly, if I do the cut at index two, I get a b a and a C.

42
00:02:58,430 --> 00:03:04,520
And finally, I could also make the cut over here at index three, which would give me a, b, a, a

43
00:03:04,520 --> 00:03:05,540
and c.

44
00:03:05,540 --> 00:03:09,590
So these are the possible ways of making one cut.

45
00:03:09,590 --> 00:03:12,590
Again these indices over here are correlated right.

46
00:03:12,590 --> 00:03:15,050
So we have zero over here and zero over here.

47
00:03:15,050 --> 00:03:22,910
And the ways in which we can cut or the places where we can make a cut ranges from zero up to three.

48
00:03:22,910 --> 00:03:29,810
Or it goes from zero up to this four minus one or I to J minus one.

49
00:03:29,810 --> 00:03:34,220
Where this over here is I, and this over here is j.

50
00:03:34,220 --> 00:03:38,840
So it goes from 0 to 3 or from I to j minus one.

51
00:03:38,840 --> 00:03:45,560
So we have discussed the different ways in which we can make one cut for a problem given to us.

52
00:03:45,590 --> 00:03:51,350
Now let's take a look at the subproblems in these different scenarios and analyze them.

53
00:03:51,650 --> 00:03:59,270
Now if the string is a, b a, a, c, we already know how to go over all the possible substrings by

54
00:03:59,270 --> 00:04:02,780
iterating over the diagonals in this depee table over here.

55
00:04:02,780 --> 00:04:05,330
So first we would go through these cells.

56
00:04:05,330 --> 00:04:09,410
Then we would go through these cells and proceed in this manner.

57
00:04:09,410 --> 00:04:11,900
So we have already discussed this multiple times.

58
00:04:11,900 --> 00:04:14,570
Now let's make an interesting observation.

59
00:04:14,570 --> 00:04:22,760
Notice that if we fill this depee table lengthwise and each cell stores the minimum cuts required for

60
00:04:22,760 --> 00:04:29,510
the substring that goes from index I to index j, which is given by the row value and the column value,

61
00:04:29,510 --> 00:04:30,440
respectively.

62
00:04:30,440 --> 00:04:36,740
Then we would already have the answers to these subproblems, because over here.

63
00:04:36,740 --> 00:04:43,190
Notice that the length of this problem over here is five, and the length of the subproblems over here

64
00:04:43,190 --> 00:04:44,600
is less than five.

65
00:04:44,600 --> 00:04:50,390
For example, the length of this string is one and the length of this string is equal to four.

66
00:04:50,390 --> 00:04:56,510
And because we are going lengthwise, we would already have calculated these before we get to a problem

67
00:04:56,510 --> 00:04:57,590
of length five.

68
00:04:57,590 --> 00:05:01,310
Because remember these strings over here have length one.

69
00:05:01,310 --> 00:05:02,930
These have length two.

70
00:05:02,960 --> 00:05:04,340
These have length three.

71
00:05:04,340 --> 00:05:05,810
And it goes on in this manner.

72
00:05:05,810 --> 00:05:13,190
So if we fill this depee table lengthwise we already have the solution to these subproblems.

73
00:05:13,190 --> 00:05:20,840
And we can use that to identify the way in which this problem over here has to be cut, such that we

74
00:05:20,840 --> 00:05:26,600
can partition it into substrings where every substring is a palindrome in itself.

75
00:05:26,600 --> 00:05:32,030
Now let's take a pointer k to iterate over these values over here.

76
00:05:32,030 --> 00:05:38,420
So k will go from zero up to three and then depee at ij in this table over here.

77
00:05:39,300 --> 00:05:47,520
It's going to equal depee at I k plus one plus dpi at k plus one j, because that's what's happening

78
00:05:47,520 --> 00:05:48,000
over here.

79
00:05:48,000 --> 00:05:54,330
For example, this over here is actually DPI at zero zero because k is equal to zero.

80
00:05:54,330 --> 00:05:57,210
And then this over here is DPI at one.

81
00:05:57,210 --> 00:06:02,280
And then over here we have four or this problem over here is DPI at zero one.

82
00:06:02,280 --> 00:06:05,130
And this is DPI at two four.

83
00:06:05,130 --> 00:06:05,580
Right.

84
00:06:05,580 --> 00:06:08,430
Because we have already stored these in the DPI table over here.

85
00:06:08,430 --> 00:06:10,350
We can just make use of them.

86
00:06:10,350 --> 00:06:14,610
So when we are doing a cut at index k we are doing one cut.

87
00:06:14,610 --> 00:06:16,530
So that's why we have plus one over here.

88
00:06:16,530 --> 00:06:22,500
And then we just need to know the minimum number of cuts required for the two sub problems at hand,

89
00:06:22,500 --> 00:06:24,870
which is something that we have already calculated.

90
00:06:24,870 --> 00:06:29,670
And we can get that from DPI at I k and DPI at k plus one j.

91
00:06:29,670 --> 00:06:37,230
And because k can take different values, we are going to identify the value of this dpi at I k plus

92
00:06:37,230 --> 00:06:39,180
one dpi at k plus one j.

93
00:06:39,180 --> 00:06:43,320
We are going to identify the value of this for these different values of k.

94
00:06:43,320 --> 00:06:50,700
So we are going to get four values and then dpi at I, j will take the minimum value of these four values.

95
00:06:50,700 --> 00:06:54,120
So this is how we are going to fill the DPI table over here.

96
00:06:54,120 --> 00:07:00,210
And this is going to be much more clearer when we do a dry run of this approach in the next video.