1
00:00:00,230 --> 00:00:02,000
Hey there and welcome back.

2
00:00:02,060 --> 00:00:09,410
Let's now discuss the tabulation approach by just using a one dimensional array for solving palindrome

3
00:00:09,410 --> 00:00:10,280
partitioning two.

4
00:00:10,310 --> 00:00:16,520
Now, before we start with the approach, let's first build the intuition behind this approach.

5
00:00:16,550 --> 00:00:19,220
So for this let's take an example.

6
00:00:19,220 --> 00:00:23,360
Let's say the string which is given to us is a b a a.

7
00:00:24,020 --> 00:00:32,030
Now the maximum number of cuts that we can do on this string over here, such that every substring is

8
00:00:32,030 --> 00:00:37,970
a substring of length one is equal to three, which would be the case where we make a cut over here,

9
00:00:37,970 --> 00:00:39,650
over here and over here.

10
00:00:39,650 --> 00:00:41,210
So that's three cuts.

11
00:00:41,210 --> 00:00:42,680
And this is the maximum.

12
00:00:42,680 --> 00:00:43,280
All right.

13
00:00:43,310 --> 00:00:46,520
Now we are going to have a pointer.

14
00:00:46,520 --> 00:00:51,350
And with the pointer we are going to iterate over the start value.

15
00:00:51,350 --> 00:00:53,540
So initially start is over here.

16
00:00:53,540 --> 00:00:56,270
And end will be kept over here itself.

17
00:00:56,910 --> 00:00:58,980
So initially start is over here.

18
00:00:58,980 --> 00:01:05,580
And we're going to check whether the string that goes from start to end is a palindrome or not.

19
00:01:05,580 --> 00:01:08,310
And we see that this is not a palindrome.

20
00:01:08,310 --> 00:01:11,790
So we retain the cuts as three itself.

21
00:01:12,150 --> 00:01:15,720
Next we move the start value from here to here.

22
00:01:15,720 --> 00:01:17,550
So initially start was over here.

23
00:01:17,550 --> 00:01:20,160
Now this is going to be moved from here to here.

24
00:01:20,160 --> 00:01:23,160
And we have start over here and end over here.

25
00:01:23,160 --> 00:01:27,480
And we are considering this substring over here which is b a.

26
00:01:27,660 --> 00:01:31,440
Now b a a is also not a palindrome.

27
00:01:31,440 --> 00:01:35,880
Therefore we retain the number of cuts required as three.

28
00:01:35,880 --> 00:01:41,640
Now the number of cuts required will only change when we get a palindrome.

29
00:01:41,640 --> 00:01:45,630
Next we again move the start index from here to here.

30
00:01:46,080 --> 00:01:54,120
And we are considering this substring over here which is a a, and we see that a a is a palindrome.

31
00:01:54,120 --> 00:02:01,830
Now because A is a palindrome, we can achieve a lower number of cuts by doing a cut over here.

32
00:02:02,220 --> 00:02:02,700
Okay.

33
00:02:02,700 --> 00:02:08,730
So doing a cut over here would split this problem into these two subproblems.

34
00:02:08,730 --> 00:02:12,360
So this subproblem over here is the string a b.

35
00:02:12,360 --> 00:02:14,490
And then we have a a over here.

36
00:02:14,490 --> 00:02:20,160
And because A is a palindrome we would need zero cuts for this part.

37
00:02:20,160 --> 00:02:28,680
And the total number of cuts that are required for this string over here would be zero plus one, plus

38
00:02:28,680 --> 00:02:36,810
the number of cuts required for converting this string into substrings where every substring is a palindrome.

39
00:02:36,810 --> 00:02:44,400
So the total number of cuts would be cuts required for the previous part, which is a B plus one, which

40
00:02:44,400 --> 00:02:50,040
is this cut over here, plus zero, which is the number of cuts required for this substring.

41
00:02:50,040 --> 00:02:53,010
And it's zero because this is a palindrome.

42
00:02:53,010 --> 00:02:57,270
Now let's say we know this or the number of cuts required for a b.

43
00:02:57,270 --> 00:03:01,200
And we will soon discuss why we will know this in this approach.

44
00:03:01,200 --> 00:03:03,480
So for now let's say we know this.

45
00:03:03,480 --> 00:03:12,060
That would indicate that the number of cuts required for a, b a is one plus one plus zero, which is

46
00:03:12,060 --> 00:03:13,080
equal to two.

47
00:03:13,110 --> 00:03:15,270
So this is one possibility.

48
00:03:15,360 --> 00:03:16,710
Now let's proceed.

49
00:03:16,710 --> 00:03:20,010
And now start is going to equal end.

50
00:03:20,040 --> 00:03:24,390
Now remember end was over here and start was over here for this case.

51
00:03:24,390 --> 00:03:29,160
Now we are again going to move this pointer and start is also going to equal a.

52
00:03:29,160 --> 00:03:31,050
And end is also equal to a.

53
00:03:31,050 --> 00:03:34,260
So the substring that we are considering is a.

54
00:03:34,260 --> 00:03:40,770
And because a is a palindrome we are going to evaluate the number of cuts required for this case.

55
00:03:40,770 --> 00:03:47,670
So the number of cuts would be the number of cuts required for the previous part which is a b a over

56
00:03:47,670 --> 00:03:49,800
here plus one.

57
00:03:49,800 --> 00:03:54,450
So this one is for this cut over here plus zero.

58
00:03:54,450 --> 00:03:55,830
And we have zero over here.

59
00:03:55,830 --> 00:03:58,200
Because this over here is a palindrome.

60
00:03:58,200 --> 00:04:02,520
Now let's say again we know the number of cuts required for the previous part.

61
00:04:02,520 --> 00:04:05,820
And that's equal to zero because a b a is a palindrome.

62
00:04:05,820 --> 00:04:07,470
So that's why we have zero over here.

63
00:04:07,470 --> 00:04:14,190
And that gives us the total number of cuts required for the string at hand with this approach as zero

64
00:04:14,190 --> 00:04:17,070
plus one plus one which is equal to one.

65
00:04:17,070 --> 00:04:18,690
So that's one over here.

66
00:04:18,690 --> 00:04:25,110
So among three two and one the minimum is equal to one.

67
00:04:25,110 --> 00:04:32,400
And therefore the minimum number of cuts required for partitioning a, b A a into substrings in a way

68
00:04:32,400 --> 00:04:36,360
that every substring is a palindrome is equal to one.

69
00:04:36,360 --> 00:04:39,420
So this is going to be the approach that we will take.

70
00:04:39,420 --> 00:04:45,810
Let's also quickly discuss why we would know the number of cuts required for the previous part over

71
00:04:45,810 --> 00:04:46,980
here and over here.

72
00:04:46,980 --> 00:04:50,400
Now again we have the example a b a a.

73
00:04:51,630 --> 00:04:55,650
Now the way that we would implement this is that we would have a DP array.

74
00:04:55,860 --> 00:05:00,570
And initially we will consider that a is the string which is given to us.

75
00:05:00,570 --> 00:05:06,600
And over here we will fill the minimum cuts required for this substring which is zero.

76
00:05:06,600 --> 00:05:12,900
Then we would consider a b as the string given to us, and the minimum number of cuts required for this

77
00:05:12,900 --> 00:05:15,600
would be filled over here, which is equal to one.

78
00:05:15,600 --> 00:05:19,800
And then we would consider a, b a and then finally a b a.

79
00:05:19,800 --> 00:05:26,490
So that's why at every point we would know the number of cuts required for a substring of lower length.

80
00:05:26,490 --> 00:05:31,650
Now we will see more of this in the next video when we do a dry run of this algorithm.

81
00:05:31,650 --> 00:05:34,680
But over here let's do one more quick observation.

82
00:05:34,680 --> 00:05:42,150
Notice over here that if a b, a A, or the string that we are considering was a palindrome, then we

83
00:05:42,150 --> 00:05:46,830
would directly know that the minimum number of cuts required would be equal to zero.

84
00:05:46,830 --> 00:05:53,490
For example, if the string given to us was a b a a, then we would not need to do a cut.

85
00:05:53,490 --> 00:05:56,130
We would directly know that the number of cuts required would be.

86
00:05:56,290 --> 00:05:59,290
Zero, because we see that these two characters are equal.

87
00:05:59,290 --> 00:06:02,770
And the middle part over here is also a palindrome.

88
00:06:02,770 --> 00:06:08,950
And which would mean that a b a a is a palindrome in itself, and therefore it would just require zero

89
00:06:08,950 --> 00:06:09,340
cuts.

90
00:06:09,340 --> 00:06:14,770
So this is also something that we would incorporate when we write the pseudo code for this approach.

91
00:06:14,770 --> 00:06:18,130
So over here we have developed the intuition.

92
00:06:18,130 --> 00:06:25,150
And we have seen that if we know the minimum cuts required for a smaller problem, we can find the minimum

93
00:06:25,150 --> 00:06:29,110
cuts required for the original problem which is a b a.

94
00:06:29,230 --> 00:06:35,650
In the next video, let's dry run this algorithm to solidify what we have learned over here and build

95
00:06:35,650 --> 00:06:37,810
a good understanding of this approach.