1
00:00:00,200 --> 00:00:05,450
Hey there and welcome back now for solving the palindrome Partitioning two question.

2
00:00:05,450 --> 00:00:08,090
We will take a look at these three approaches.

3
00:00:08,090 --> 00:00:10,670
First we will take a look at the recursion approach.

4
00:00:10,670 --> 00:00:12,380
Then we will memorize it.

5
00:00:12,380 --> 00:00:16,130
And then we will discuss the tabulation approach for solving this question.

6
00:00:16,130 --> 00:00:22,640
And when we discuss the tabulation approach we will try to solve this question both using a 2D DP array

7
00:00:22,640 --> 00:00:25,070
as well as using a one dimensional array.

8
00:00:25,070 --> 00:00:27,770
So let's get started with the recursion approach.

9
00:00:27,890 --> 00:00:33,470
So for this let's say the input which is given to us is a b a c.

10
00:00:33,950 --> 00:00:38,360
Now let's try to draw the recursion tree for this input.

11
00:00:38,450 --> 00:00:44,840
The way that we are going to approach this is we are going to see where we can make a partition such

12
00:00:44,840 --> 00:00:50,810
that the string that we are going to get on the left side after making a partition is in fact a palindrome.

13
00:00:50,810 --> 00:00:57,020
For example, notice that we could make a partition over here, and then over here we are getting a

14
00:00:57,020 --> 00:00:57,650
palindrome.

15
00:00:57,650 --> 00:00:58,070
Right.

16
00:00:58,070 --> 00:00:59,810
So this is a possibility.

17
00:00:59,810 --> 00:01:07,010
So if you are doing this then the subproblem that remains would be this string over here which is b

18
00:01:07,010 --> 00:01:07,820
a a c.

19
00:01:07,820 --> 00:01:13,160
And we will have to add one to it because we are making a partition over here in a similar manner.

20
00:01:13,160 --> 00:01:18,710
We could also have done the partition over here because a, b, a is a palindrome.

21
00:01:18,710 --> 00:01:23,210
And if we do that, then the problem that remains is a C.

22
00:01:23,210 --> 00:01:28,010
And the solution would be one plus the number of partitions required for a C.

23
00:01:28,010 --> 00:01:32,330
And we are doing one plus over here because we have done a partition over here.

24
00:01:32,330 --> 00:01:34,370
So there are these two possibilities.

25
00:01:34,370 --> 00:01:39,530
And again the approach is that we will be iterating over the characters from left to right.

26
00:01:39,530 --> 00:01:44,960
And we are going to explore whether we can make a partition and we can make a partition.

27
00:01:44,960 --> 00:01:51,530
If we see that the string on the left hand side will be a palindrome, which is the case over here and

28
00:01:51,530 --> 00:01:52,610
the case over here.

29
00:01:52,610 --> 00:01:55,850
So that's why we are getting only two possibilities over here.

30
00:01:55,850 --> 00:02:00,950
And finally we would have to return the minimum among these two solutions.

31
00:02:00,950 --> 00:02:05,390
So this over here will finally give us a number or the number of partitions required.

32
00:02:05,390 --> 00:02:07,430
And this also will give us a number.

33
00:02:07,430 --> 00:02:12,770
And because we are asked to identify the minimum number of cuts required, we would have to identify

34
00:02:12,770 --> 00:02:16,010
the minimum between these two and return that value.

35
00:02:16,010 --> 00:02:18,350
Now let's go down this branch over here.

36
00:02:18,350 --> 00:02:23,300
Now remember we are only dealing with this subproblem over here which is b a, a c.

37
00:02:23,360 --> 00:02:25,700
Again we are going to go from left to right.

38
00:02:25,700 --> 00:02:32,480
And our aim is to identify the places where we can make a cut such that the string to the left of it

39
00:02:32,480 --> 00:02:33,800
is a palindrome.

40
00:02:33,800 --> 00:02:40,280
Now, for example, we could make a cut over here and if we do that, this subproblem over here will

41
00:02:40,280 --> 00:02:44,810
change to one plus a, a, c because this is the remaining string.

42
00:02:44,810 --> 00:02:49,670
And then we have to do one plus over here because we have done a cut over here.

43
00:02:49,670 --> 00:02:56,540
Also notice that there is no other place where we could do a cut such that the string on the left hand

44
00:02:56,540 --> 00:02:58,310
side will become a palindrome.

45
00:02:58,310 --> 00:03:05,300
So this over here will have only one branch, and then we can go further down to solve this subproblem

46
00:03:05,300 --> 00:03:07,910
over here, which is the string a, a c.

47
00:03:08,090 --> 00:03:11,090
Now over here again we move from left to right.

48
00:03:11,090 --> 00:03:16,070
And we are trying to identify positions where we can make cuts such that the string to the left is a

49
00:03:16,070 --> 00:03:16,760
palindrome.

50
00:03:16,760 --> 00:03:21,050
And we see that we could do a cut over here as well as a cut over here.

51
00:03:21,050 --> 00:03:28,880
So the two ways in which this can be partitioned is one plus a C and one plus c one plus a C.

52
00:03:28,880 --> 00:03:32,150
Because if you do the cut over here this is the remaining string.

53
00:03:32,150 --> 00:03:35,420
And then if you do the cut over here we just have C left.

54
00:03:35,420 --> 00:03:38,720
So these are the two branches that this will have.

55
00:03:38,720 --> 00:03:45,080
And then finally we would be returning the minimum among these two for finding the answer for this problem

56
00:03:45,080 --> 00:03:45,590
a c.

57
00:03:45,920 --> 00:03:51,680
And over here we have already reached the end of this branch because we just have one more character

58
00:03:51,680 --> 00:03:59,090
over here and over here a C for solving a C, we can again make one more cut and we would get one plus

59
00:03:59,120 --> 00:03:59,510
C.

60
00:04:01,050 --> 00:04:06,390
Let's also complete this branch over here because we have one plus AC to solve AC.

61
00:04:06,420 --> 00:04:10,260
We would need one more cut and this becomes one plus C.

62
00:04:10,350 --> 00:04:14,910
So this is how the recursion tree would look like for this problem.

63
00:04:14,910 --> 00:04:19,440
And notice that we are actually following a backtracking approach over here.

64
00:04:19,440 --> 00:04:23,640
Or more technically, a pruned recursion approach.

65
00:04:23,700 --> 00:04:30,000
Now I'm calling this pruned recursion because notice that we are pruning branches that don't lead to

66
00:04:30,000 --> 00:04:30,750
a solution.

67
00:04:30,750 --> 00:04:37,200
For example, over here, having a cut at this place would not lead to a solution because this is not

68
00:04:37,200 --> 00:04:37,890
a palindrome.

69
00:04:37,890 --> 00:04:44,940
So the branch one plus A, a c was pruned because this is not a viable solution.

70
00:04:44,940 --> 00:04:47,640
So that's why this is a pruned recursive approach.

71
00:04:47,640 --> 00:04:53,070
And again we are not calling it strictly backtracking because we are not making changes to the state

72
00:04:53,070 --> 00:04:53,910
of the problem.

73
00:04:53,910 --> 00:04:58,830
What we are doing is just we are using pointers to go down the branches of the recursion tree.

74
00:04:58,830 --> 00:05:01,170
So this is a pruned recursive approach.

75
00:05:01,170 --> 00:05:08,580
And the time complexity of this approach is going to be of the order of n into two to the power n.

76
00:05:08,580 --> 00:05:09,900
Now why is that so?

77
00:05:09,900 --> 00:05:16,080
First of all, previously we have discussed that if we are given a string of length n, then the number

78
00:05:16,080 --> 00:05:21,900
of partitions that we can have for this string would be two to the power n minus one.

79
00:05:21,900 --> 00:05:23,730
So I'm not going to repeat it over here.

80
00:05:23,730 --> 00:05:26,070
We have already discussed this in a previous video.

81
00:05:26,070 --> 00:05:29,940
So the number of partitions is going to equal two to the power n minus one.

82
00:05:29,940 --> 00:05:35,280
And we can say that this value over here is of the order of two to the power n.

83
00:05:35,280 --> 00:05:37,290
Now let's make some space over here.

84
00:05:38,020 --> 00:05:45,010
So we have seen that the number of partitions is of the order of two to the power n, and for each of

85
00:05:45,010 --> 00:05:50,620
these partitions we'll have to do palindrome checks on various substrings.

86
00:05:50,650 --> 00:05:57,850
Now for each partition, this part over here, that is the various palindrome checks that we'll have

87
00:05:57,850 --> 00:05:59,920
to do for various substrings.

88
00:05:59,920 --> 00:06:07,780
This together for a partition will require work of the order of n, because n is the length of the string

89
00:06:07,780 --> 00:06:13,780
which is given to us, and because we'll have to do this much work for each partition, and because

90
00:06:13,780 --> 00:06:16,300
we have two to the power n partitions.

91
00:06:16,300 --> 00:06:22,720
The total time complexity of this approach is of the order of n into two to the power n.