1
00:00:00,110 --> 00:00:01,010
Welcome back.

2
00:00:01,010 --> 00:00:06,500
Let's now implement the recursive solution for solving palindrome partitioning two.

3
00:00:06,530 --> 00:00:06,950
Okay.

4
00:00:06,950 --> 00:00:10,370
So this solution over here is not going to use dynamic programming.

5
00:00:10,370 --> 00:00:15,680
And we will be needing a function to check whether a particular substring is a palindrome.

6
00:00:15,680 --> 00:00:17,870
So let's just call it a palindrome.

7
00:00:18,640 --> 00:00:23,140
And to this function we will be passing the start and end index.

8
00:00:23,170 --> 00:00:23,590
Okay.

9
00:00:23,590 --> 00:00:29,800
So again basically we will be considering the substring that starts at this particular index and goes

10
00:00:29,800 --> 00:00:32,260
up to this particular index in the given string.

11
00:00:32,260 --> 00:00:32,650
All right.

12
00:00:32,680 --> 00:00:36,910
Now because this function is pretty straightforward let's just go ahead and implement it.

13
00:00:36,910 --> 00:00:42,430
So over here we are going to have a while loop that will keep looping as long as start is less than

14
00:00:42,430 --> 00:00:43,450
end okay.

15
00:00:43,450 --> 00:00:50,740
And over here we are going to check whether s at start is not equal to s at end.

16
00:00:50,920 --> 00:00:55,180
Because if we see that this is true then we can just return false.

17
00:00:56,310 --> 00:01:02,160
But if this is not the case, then we proceed and we are going to move both the pointers okay.

18
00:01:02,160 --> 00:01:05,730
So start will be incremented and end will be decremented.

19
00:01:05,730 --> 00:01:06,600
And that's it.

20
00:01:06,600 --> 00:01:12,270
And again if we come out of the while loop and we are not able to return false, then over here we are

21
00:01:12,270 --> 00:01:13,770
just going to return true.

22
00:01:14,850 --> 00:01:19,830
So this is the function that we will use to check whether a particular substring is a palindrome or

23
00:01:19,830 --> 00:01:20,280
not.

24
00:01:20,280 --> 00:01:25,620
Now let's go ahead and write the main function, which is the function that we will be recursively calling.

25
00:01:25,620 --> 00:01:27,360
Let's just call it partitions.

26
00:01:28,170 --> 00:01:29,310
And to this function.

27
00:01:29,310 --> 00:01:33,330
Also we have to pass the start and end index okay.

28
00:01:33,330 --> 00:01:35,820
And let's write the details of this function later.

29
00:01:35,820 --> 00:01:39,270
And over here we will be calling this function for the first time.

30
00:01:39,270 --> 00:01:45,840
And when we do that we will be passing the first index of string s which is zero, and the last index

31
00:01:45,840 --> 00:01:49,170
of the given string which is s dot length minus one.

32
00:01:49,170 --> 00:01:49,590
All right.

33
00:01:49,590 --> 00:01:55,230
And again we will be writing this function in such a way that we will be getting back the number of

34
00:01:55,230 --> 00:02:00,360
cuts or the minimum number of cuts that we have to make for ensuring that the given string has been

35
00:02:00,360 --> 00:02:01,860
partitioned into palindromes.

36
00:02:01,860 --> 00:02:04,980
And therefore we can just return whatever we get over here.

37
00:02:04,980 --> 00:02:07,110
So this is the skeleton of the solution.

38
00:02:07,110 --> 00:02:09,300
Now let's go ahead and write the details over here.

39
00:02:09,300 --> 00:02:14,880
So we have to write the base case as well as the recursive case over here okay.

40
00:02:14,880 --> 00:02:21,030
Now the base case will be the scenario where either start and end are equal.

41
00:02:21,030 --> 00:02:26,310
Because if that is the case, then the substring that we are considering consists just of one character,

42
00:02:26,310 --> 00:02:28,680
and such a substring is a palindrome.

43
00:02:28,710 --> 00:02:34,680
Or if that is not the case, then we will just check whether the substring that starts at start and

44
00:02:34,680 --> 00:02:40,800
goes up to end is a palindrome, because in either of these two cases, we would not require any cut.

45
00:02:40,800 --> 00:02:41,160
Okay.

46
00:02:41,160 --> 00:02:49,800
So we can say if start is equal to end or is palindrome start comma end.

47
00:02:49,950 --> 00:02:55,740
So if this is true, if either of these is true, then we will just return zero because we would not

48
00:02:55,740 --> 00:02:57,270
require any cut okay.

49
00:02:57,270 --> 00:03:01,920
And again we are making use of this function is palindrome which is what we have written over here.

50
00:03:01,920 --> 00:03:06,090
Now if this is not the case then we proceed with the recursive case.

51
00:03:06,090 --> 00:03:13,110
And again our aim is to identify the minimum number of cuts that we have to do to partition the substring

52
00:03:13,110 --> 00:03:19,200
that starts at start and goes up to end, such that all the partitions are palindromes.

53
00:03:19,470 --> 00:03:21,870
Now to start with, let's have a variable.

54
00:03:21,870 --> 00:03:24,120
Let's just call it minimum cuts.

55
00:03:24,480 --> 00:03:28,620
And this is going to be equal to end minus start.

56
00:03:28,620 --> 00:03:30,750
And again what is it that we are doing over here.

57
00:03:30,750 --> 00:03:32,040
Let me take an example.

58
00:03:32,040 --> 00:03:35,730
Let's say the string which is given to us is a void okay.

59
00:03:35,730 --> 00:03:42,690
So in this case notice that the maximum number of cuts that we need to do to ensure that all the cuts

60
00:03:42,690 --> 00:03:44,400
are palindromes would be three.

61
00:03:44,400 --> 00:03:44,580
Right.

62
00:03:44,580 --> 00:03:49,710
Because if you do a cut over here, a cut over here and a cut over here, then we have ensured that

63
00:03:49,710 --> 00:03:54,810
all the partitions consist of single characters and hence all of them are palindromes.

64
00:03:54,810 --> 00:04:00,270
Okay, so that's why over here we are assigning the maximum possible value which we can get by just

65
00:04:00,270 --> 00:04:02,610
subtracting the start index from the end index.

66
00:04:02,610 --> 00:04:06,180
So we are assigning the maximum possible value to minimum cuts.

67
00:04:06,180 --> 00:04:12,360
And later if we get something lower than that we will replace minimum cuts with the lower value.

68
00:04:12,360 --> 00:04:14,730
So that's the approach that we are taking over here.

69
00:04:14,730 --> 00:04:19,050
Now we are going to have a for loop and we will need a variable.

70
00:04:19,050 --> 00:04:20,760
Let's just call it end index.

71
00:04:20,760 --> 00:04:25,140
And this is going to equal start which is what is given to us over here.

72
00:04:25,140 --> 00:04:28,800
And it will keep going till end minus one okay.

73
00:04:28,800 --> 00:04:30,720
So end index less than end.

74
00:04:30,720 --> 00:04:34,080
And we have end index plus plus okay.

75
00:04:34,080 --> 00:04:37,320
So notice it's going only till end minus one.

76
00:04:37,320 --> 00:04:43,920
And that's because if it were to go up to end then if you are considering a substring that goes from

77
00:04:43,920 --> 00:04:47,550
start up to end index it would be this substring itself.

78
00:04:47,550 --> 00:04:49,260
So that's why we are not taking that okay.

79
00:04:49,260 --> 00:04:51,870
So it will go only up to n minus one.

80
00:04:51,870 --> 00:04:59,970
And now our aim is to see whether we can get a palindrome starting at start and going up to end index.

81
00:04:59,970 --> 00:05:01,920
So we are going to do that check over here.

82
00:05:01,920 --> 00:05:06,600
So if this palindrome start comma end index.

83
00:05:06,600 --> 00:05:12,780
So if we can get a palindrome in this manner then we will go ahead and make a cut over there and recursively

84
00:05:12,780 --> 00:05:18,810
call the partitions function to go deeper down that particular branch in the recursive tree okay.

85
00:05:18,810 --> 00:05:26,760
So if this is true then we will say minimum cuts is equal to math dot min between what we already have

86
00:05:26,760 --> 00:05:33,720
in minimum cuts and the number of cuts that would be required as per this particular partition that

87
00:05:33,720 --> 00:05:34,890
we are going to make over here.

88
00:05:34,890 --> 00:05:35,220
Okay.

89
00:05:35,220 --> 00:05:37,770
So that would be one plus.

90
00:05:37,770 --> 00:05:40,470
Again we are calling the partitions function recursively.

91
00:05:40,470 --> 00:05:45,780
And now we are going to only pass the indices beyond end index.

92
00:05:45,780 --> 00:05:49,740
And that is why the start index in this case would be end index plus one.

93
00:05:49,740 --> 00:05:52,710
And the end index is end itself okay.

94
00:05:52,710 --> 00:05:55,890
So again this over here will give us the number of cut.

95
00:05:56,250 --> 00:06:00,960
Required, as per this particular branch, that we are going deeper and deeper on the recursive tree

96
00:06:01,080 --> 00:06:04,590
to ensure that all the partitions are palindromes.

97
00:06:04,590 --> 00:06:05,040
Okay.

98
00:06:05,040 --> 00:06:11,550
And in this way we will ensure that ultimately minimum cuts will give us the minimum between the various

99
00:06:11,550 --> 00:06:15,930
branches that we can take such that the partitions are palindromes.

100
00:06:15,930 --> 00:06:20,550
And once we are out of this for loop, we would just need to return minimum cuts.

101
00:06:20,850 --> 00:06:21,720
And that's it.

102
00:06:21,720 --> 00:06:23,280
So this should solve the question.

103
00:06:23,280 --> 00:06:27,420
Now let's go ahead and run this code and see if it's passing all the test cases.

104
00:06:28,230 --> 00:06:29,910
And you can see that it's working.

105
00:06:29,910 --> 00:06:31,740
It's passing all the test cases.