1
00:00:01,080 --> 00:00:02,910
Hey there and welcome back.

2
00:00:02,910 --> 00:00:09,360
In this video, let's do a dry run of the second tabulation approach that we have discussed for solving

3
00:00:09,360 --> 00:00:10,800
palindrome partitioning two.

4
00:00:10,800 --> 00:00:15,810
So for this let's say the input given to us is a b a a, C.

5
00:00:15,810 --> 00:00:20,580
And as we have discussed we will just use a one dimensional DP array.

6
00:00:20,730 --> 00:00:27,570
So initially we will consider only this substring over here which has just one character a.

7
00:00:28,080 --> 00:00:31,380
Now we know that this is a palindrome.

8
00:00:31,380 --> 00:00:34,290
And therefore over here we will fill zero.

9
00:00:34,290 --> 00:00:42,900
So in the DP array at every cell we are going to fill the minimum number of cuts required for the substring

10
00:00:42,900 --> 00:00:46,050
that goes from zero up to index I.

11
00:00:46,080 --> 00:00:52,740
So if I is the index that we are considering, every cell over here will be filled with the minimum

12
00:00:52,740 --> 00:00:59,820
cuts required to partition the string that goes from zero up to index I in a way that every substring

13
00:00:59,820 --> 00:01:00,810
is a palindrome.

14
00:01:00,810 --> 00:01:03,900
So we have seen that over here we will fill the value zero.

15
00:01:03,900 --> 00:01:10,830
Now we will proceed with the next substring which starts at index zero and goes up to index one.

16
00:01:10,830 --> 00:01:16,950
So ab is the substring that we are considering now because a and b are not equal.

17
00:01:16,950 --> 00:01:21,930
So because this is not a palindrome we will consider making one cut.

18
00:01:21,930 --> 00:01:25,290
And again we are doing this because AB is not a palindrome.

19
00:01:25,290 --> 00:01:32,280
So when we move the start index and have it point to this index over here and end was already over here,

20
00:01:32,280 --> 00:01:34,590
we are just considering this substring.

21
00:01:34,590 --> 00:01:37,500
And we see that this is in fact a palindrome.

22
00:01:37,500 --> 00:01:44,160
Therefore, in this case the number of cuts required would be one plus the number of cuts required for

23
00:01:44,160 --> 00:01:47,790
the previous part, which is just a and for a.

24
00:01:47,820 --> 00:01:52,650
We know that we don't need to do any cuts, and we already have that in the DP table over here.

25
00:01:52,650 --> 00:01:58,800
So in this case the number of cuts required is one plus zero which is equal to one.

26
00:01:58,800 --> 00:02:01,500
So we can go ahead and fill one over here.

27
00:02:01,500 --> 00:02:06,750
Notice that initially for string AB the maximum number of cuts is one itself.

28
00:02:06,750 --> 00:02:11,070
And over here we have seen that between 1 and 1 the minimum is also one.

29
00:02:11,070 --> 00:02:13,620
So we go ahead and fill one over here.

30
00:02:13,620 --> 00:02:17,430
Now let's proceed to the next substring which is ab a.

31
00:02:17,730 --> 00:02:23,220
Now the maximum number of cuts over here would be two which is one and two.

32
00:02:23,220 --> 00:02:28,170
But again over here we notice that ab a in itself is a palindrome.

33
00:02:28,170 --> 00:02:31,830
And therefore we would not require any cut for this substring.

34
00:02:31,830 --> 00:02:34,650
And we can go ahead and fill zero over here.

35
00:02:34,920 --> 00:02:38,100
So we have zero over here in the DP table.

36
00:02:38,100 --> 00:02:42,840
And then we proceed to the next substring which is ab a.

37
00:02:42,960 --> 00:02:45,780
Now ab a is not a palindrome.

38
00:02:45,780 --> 00:02:49,980
So the maximum number of cuts that can be done for this substring is three.

39
00:02:49,980 --> 00:02:52,890
So cuts is set initially to the value three.

40
00:02:52,890 --> 00:02:58,710
And then we're going to explore the different possible substrings by moving the start value.

41
00:02:58,710 --> 00:03:02,160
So initially start is over here and end is over here.

42
00:03:02,160 --> 00:03:04,800
And we have seen that this over here is not a palindrome.

43
00:03:04,800 --> 00:03:07,680
So we move start and start comes over here.

44
00:03:07,680 --> 00:03:10,020
So AB A is not a palindrome.

45
00:03:10,020 --> 00:03:11,340
So start has been moved.

46
00:03:11,340 --> 00:03:16,260
And we are considering b a a and b a is also not a palindrome.

47
00:03:16,260 --> 00:03:22,380
Again we move the value of start and we are considering a a and a is in fact a palindrome.

48
00:03:22,380 --> 00:03:29,670
Therefore, the number of cuts required in this scenario is one plus the number of cuts required for

49
00:03:29,670 --> 00:03:33,960
AB, which is the previous part, and for AB.

50
00:03:33,990 --> 00:03:39,090
From our DP table, we know that the number of cuts required is equal to one.

51
00:03:39,090 --> 00:03:45,750
So the number of cuts required in this scenario is one plus one which is equal to two.

52
00:03:45,750 --> 00:03:46,860
Now we proceed.

53
00:03:46,860 --> 00:03:50,640
So again remember at this point start is over here and end is over here.

54
00:03:50,640 --> 00:03:52,710
Now we are again going to move this pointer.

55
00:03:52,710 --> 00:03:54,330
And it's going to point at a.

56
00:03:54,360 --> 00:03:56,970
So the string that we are considering is a.

57
00:03:56,970 --> 00:04:01,560
Now this is a palindrome because it's a substring of length one.

58
00:04:01,560 --> 00:04:05,880
And therefore let's consider the number of cuts required in this scenario.

59
00:04:05,880 --> 00:04:11,100
So the number of cuts required for this scenario would be the number of cuts required for the previous

60
00:04:11,100 --> 00:04:15,060
part, which is AB a plus one plus zero.

61
00:04:15,060 --> 00:04:17,790
Because again we don't need any cuts for this part.

62
00:04:17,790 --> 00:04:22,980
So the total number of cuts required is the number of cuts required for ABBA plus one.

63
00:04:22,980 --> 00:04:27,090
And for ABBA, we know that we don't need to do any cuts.

64
00:04:27,090 --> 00:04:35,850
So this over here becomes zero plus one, which is equal to one now among three, two and one, the

65
00:04:35,850 --> 00:04:42,240
minimum value is one, and therefore the minimum cuts required for AB a a is equal to one.

66
00:04:42,240 --> 00:04:44,790
And we can fill this value over here.

67
00:04:45,030 --> 00:04:49,590
Now let's proceed to the next problem which is a b a a c.

68
00:04:49,620 --> 00:04:52,320
Now we see that this is not a palindrome.

69
00:04:52,320 --> 00:04:57,990
And therefore we initialize cuts to the maximum number of cuts which is equal to four.

70
00:04:57,990 --> 00:05:00,360
So cuts now is equal to four.

71
00:05:00,600 --> 00:05:07,380
And we have seen that a, b, a c is not a palindrome, then we are going to consider back by moving

72
00:05:07,380 --> 00:05:13,020
the start index from here to here and back is also not a palindrome.

73
00:05:13,020 --> 00:05:19,530
Again, we will move the start index and we are considering a a c a a c is also not a palindrome.

74
00:05:19,530 --> 00:05:23,760
So we again move the start index and we are considering a C.

75
00:05:24,060 --> 00:05:26,340
A c is also not a palindrome.

76
00:05:26,340 --> 00:05:31,770
Therefore we will move the start index and we are just considering c and C is a palindrome.

77
00:05:31,770 --> 00:05:37,350
So the number of cuts required in this case would be the number of cuts required for the previous part,

78
00:05:37,350 --> 00:05:42,300
which is a, b a, a plus one, and for a b a a.

79
00:05:42,300 --> 00:05:45,900
From the DP table we know that we just need one cut.

80
00:05:45,900 --> 00:05:50,490
So this over here simplifies to one plus one which is equal to two.

81
00:05:50,490 --> 00:05:53,970
And between 4 and 2 two is the minimum value.

82
00:05:53,970 --> 00:05:58,530
And therefore we feel that over here and we are done filling our DP table.

83
00:05:58,530 --> 00:06:01,170
And this over here gives us the answer.

84
00:06:01,170 --> 00:06:05,010
Or the last value in the DP table gives us the answer.

85
00:06:05,010 --> 00:06:11,550
Because notice over here this represents the minimum cuts required for the string that starts at index

86
00:06:11,550 --> 00:06:14,370
zero and goes up to this index over here.

87
00:06:14,370 --> 00:06:16,830
And that's 0123 and four.

88
00:06:16,830 --> 00:06:22,920
So this over here represents the number of cuts required for the string that goes from zero to index

89
00:06:22,920 --> 00:06:25,830
four, which is actually the problem given to us.

90
00:06:25,830 --> 00:06:28,710
So the answer to this question is equal to two.

91
00:06:28,710 --> 00:06:34,050
And I'm sure this dry run has helped solidify learning how this algorithm works.