1
00:00:00,440 --> 00:00:02,300
Hey there and welcome back!

2
00:00:02,510 --> 00:00:08,630
In the previous videos, we have discussed the approach that we can take to solve the palindrome partitioning

3
00:00:08,630 --> 00:00:09,260
question.

4
00:00:09,650 --> 00:00:15,260
Let's now discuss the space and time complexity of the approach that we came up with.

5
00:00:15,290 --> 00:00:22,340
So when it comes to the space complexity, notice that it's going to be of the order of n square, because

6
00:00:22,340 --> 00:00:24,680
we have to build this DP table.

7
00:00:24,680 --> 00:00:27,620
And this takes space of the order of n square.

8
00:00:28,070 --> 00:00:34,850
Also remember the backtracking part that we discussed will take up space on the recursive call stack.

9
00:00:34,850 --> 00:00:39,980
But notice over here the maximum depth of this is just going to be of the order of n.

10
00:00:39,980 --> 00:00:47,060
And because n is less than n square, we can say that the space complexity of this solution is of the

11
00:00:47,060 --> 00:00:48,200
order of n square.

12
00:00:48,230 --> 00:00:50,720
Now what about the time complexity?

13
00:00:50,750 --> 00:00:57,500
The time complexity of this solution is of the order of two to the power n into n.

14
00:00:57,500 --> 00:00:59,570
Now let's try to understand this.

15
00:00:59,600 --> 00:01:06,680
Now what are the things that take up computation, or which are the things in the solution that we came

16
00:01:06,680 --> 00:01:09,410
up with in which the algorithm does work?

17
00:01:09,410 --> 00:01:15,320
So there is the backtracking part, and there is the part where we build the DP array over here.

18
00:01:15,320 --> 00:01:22,700
We have previously seen that building the 2d dp array has a time complexity of the order of n square.

19
00:01:22,700 --> 00:01:25,250
So we have previously already discussed this.

20
00:01:25,250 --> 00:01:27,320
So I'm not going to repeat it over here.

21
00:01:27,350 --> 00:01:30,110
Now let's take a look at the backtracking part.

22
00:01:30,470 --> 00:01:35,960
For this let's have the recursion tree that we previously discussed placed over here.

23
00:01:35,960 --> 00:01:39,200
And the input string was aa ba.

24
00:01:39,920 --> 00:01:47,360
Now first let's try to identify the number of ways in which a BA can be partitioned.

25
00:01:47,390 --> 00:01:52,070
Now again we are trying to find the upper bound or the worst case scenario.

26
00:01:52,100 --> 00:01:57,320
Now to think about the number of ways in which a BA can be partitioned.

27
00:01:57,320 --> 00:02:02,360
Imagine that there are three roads kept at these places.

28
00:02:02,870 --> 00:02:08,150
So I have one road over here, one road over here, and one road over here.

29
00:02:08,420 --> 00:02:15,650
Now, to identify the different ways in which I can partition this string, I just need to identify

30
00:02:15,650 --> 00:02:20,780
the number of ways in which I can pick three roads among these three roads.

31
00:02:20,810 --> 00:02:24,650
The number of ways in which I can pick two roads among these three roads.

32
00:02:24,650 --> 00:02:30,050
The number of ways in which I can pick just one road among these three roads, and the number of ways

33
00:02:30,050 --> 00:02:33,560
in which I can pick zero roads among these three roads.

34
00:02:33,710 --> 00:02:41,360
And once we have found these values, we just need to add these ways of partitioning the input string.

35
00:02:41,390 --> 00:02:44,780
Now again, let me try to explain this a little bit further.

36
00:02:44,780 --> 00:02:51,830
So if we were to pick three roads from the three roads available over here, that would be equivalent

37
00:02:51,830 --> 00:02:57,200
to partitioning A, A, B, a in this manner because we have all the three roads.

38
00:02:57,200 --> 00:02:59,510
So that gives us a, a, B, a.

39
00:02:59,630 --> 00:03:06,530
But if I just pick two roads, then one way of picking two roads would be I just pick the first two

40
00:03:06,530 --> 00:03:07,130
roads.

41
00:03:07,130 --> 00:03:10,790
So this gives me the partition A, A and BA.

42
00:03:10,820 --> 00:03:18,200
Now if I pick two roads in this manner then this gives me the partition a, a b a.

43
00:03:18,200 --> 00:03:20,630
So notice that these are separate right.

44
00:03:20,630 --> 00:03:28,550
So that's why if we can just identify the different ways in which we can pick 3 or 2 or 1 or 0 roads

45
00:03:28,550 --> 00:03:36,260
from these three roads, it would give us all the ways of partitioning the string which is given to

46
00:03:36,260 --> 00:03:36,680
us.

47
00:03:36,770 --> 00:03:41,210
So let's now go ahead and write down the different ways in which we can do this.

48
00:03:41,210 --> 00:03:47,240
So if I want to pick three roads out of the three roads, I can do that only in one way.

49
00:03:47,240 --> 00:03:52,220
So if I do that, the partition that I get is a, a, B, a.

50
00:03:52,730 --> 00:03:58,910
If I go ahead and just pick two roads, I could pick these two, I could pick these two, or I could

51
00:03:58,910 --> 00:03:59,960
pick these two.

52
00:03:59,960 --> 00:04:04,520
So that gives me three ways of partitioning the input string.

53
00:04:04,520 --> 00:04:10,010
So that's a a b a a a b a and a a b a.

54
00:04:10,010 --> 00:04:16,250
So these are the three ways in which I can partition the input string by just picking two roads out

55
00:04:16,250 --> 00:04:17,840
of these three roads.

56
00:04:17,870 --> 00:04:24,230
Now if I can just pick one road I can pick just this one or this one or this one.

57
00:04:24,230 --> 00:04:28,160
So that gives me again three ways of partitioning the input string.

58
00:04:28,160 --> 00:04:33,710
And the three ways are a, a, b a a a b a and a a b a.

59
00:04:33,890 --> 00:04:40,670
And finally, if I can just pick zero roads then it gives me the partition a a b a.

60
00:04:40,760 --> 00:04:47,570
So these are all the possible partitions which can be executed on the input string.

61
00:04:47,570 --> 00:04:49,430
So this is one way.

62
00:04:49,430 --> 00:04:50,960
This is three ways.

63
00:04:50,960 --> 00:04:52,640
Over here we have three ways.

64
00:04:52,640 --> 00:04:54,800
And over here we have one way.

65
00:04:54,830 --> 00:04:56,990
Now how do we get these numbers.

66
00:04:56,990 --> 00:04:59,870
It's not always convenient to go ahead and write it.

67
00:05:00,020 --> 00:05:01,130
Out and check it.

68
00:05:01,130 --> 00:05:05,090
So over here what we're doing is selecting three things.

69
00:05:05,090 --> 00:05:10,460
Three rods out of three rods which is 3C3.

70
00:05:11,570 --> 00:05:16,700
And over here I'm just selecting two rods out of these three rods.

71
00:05:16,700 --> 00:05:18,710
And I can do this in three.

72
00:05:18,740 --> 00:05:19,790
See two ways.

73
00:05:19,790 --> 00:05:25,850
And over here I'm selecting one rod out of these three rods which can be done in three.

74
00:05:25,880 --> 00:05:27,020
See one way.

75
00:05:27,020 --> 00:05:32,870
And over here I'm selecting zero rods out of these three rods which can be done in three.

76
00:05:32,900 --> 00:05:34,760
See zero ways okay.

77
00:05:34,760 --> 00:05:35,480
So I have three.

78
00:05:35,510 --> 00:05:36,470
See three over here.

79
00:05:36,470 --> 00:05:36,890
Three.

80
00:05:36,890 --> 00:05:38,300
See two over here three.

81
00:05:38,300 --> 00:05:41,240
See one over here and three see zero over here.

82
00:05:41,330 --> 00:05:45,710
Now I just need to add these up so it goes from three.

83
00:05:45,740 --> 00:05:48,200
See zero up to three see three.

84
00:05:48,200 --> 00:05:52,430
And in a previous video we have discussed the meaning of NCR.

85
00:05:52,430 --> 00:05:55,340
So let's go ahead and add these up.

86
00:05:55,340 --> 00:06:00,950
So we get 3C0 plus 3C1 plus 3C2 plus 3C3.

87
00:06:03,320 --> 00:06:08,030
And in this case we had four characters in the input string.

88
00:06:08,030 --> 00:06:14,840
So notice that this three is actually n minus one, where n is the length of the input string.

89
00:06:14,840 --> 00:06:20,720
So it goes from n minus one zero up to n minus 1CN minus one.

90
00:06:20,720 --> 00:06:25,340
Now this series over here is a famous series in maths.

91
00:06:25,340 --> 00:06:31,610
So if we have NC0 plus NC1 etcetera up to n c n.

92
00:06:31,610 --> 00:06:35,870
And that's what we have over here instead of n we just have n minus one.

93
00:06:35,870 --> 00:06:40,520
So this over here sums up to two to the power n.

94
00:06:40,520 --> 00:06:43,940
And because over here we have n minus one instead of n.

95
00:06:43,940 --> 00:06:48,500
This series over here sums up to two to the power n minus one.

96
00:06:49,290 --> 00:06:50,850
So what is this?

97
00:06:50,850 --> 00:06:52,410
Two to the power n minus one.

98
00:06:52,410 --> 00:06:59,430
This actually is the maximum or the upper bound of the number of partitions that we can do.

99
00:06:59,430 --> 00:07:04,680
If we are given a string of length n again notice how did we find this?

100
00:07:04,680 --> 00:07:11,340
We found the various ways of partitioning the input string by taking three out of these three rods,

101
00:07:11,340 --> 00:07:16,920
two out of these three rods, one out of these three rods and zero out of these three rods.

102
00:07:16,920 --> 00:07:23,310
So this gave us all the various possible ways of partitioning the input string, which is nothing but

103
00:07:23,310 --> 00:07:29,100
n minus one, c zero, n minus one, c one, etc. up to n minus one, c n minus one.

104
00:07:29,100 --> 00:07:33,330
And when we add these up we get two to the power n minus one.

105
00:07:33,330 --> 00:07:40,650
So the maximum number of partitions that we can do is of the order of two to the power n, because this

106
00:07:40,650 --> 00:07:42,480
is two to the power n minus one.

107
00:07:42,780 --> 00:07:47,430
Now let's come back to the part where we were discussing the time complexity.

108
00:07:47,430 --> 00:07:54,060
We said that the time complexity is equal to the time complexity required for the backtracking part,

109
00:07:54,060 --> 00:07:58,440
plus the time complexity for building the DP table over here.

110
00:07:58,440 --> 00:08:01,200
And this part was of the order of N square.

111
00:08:01,200 --> 00:08:03,720
And we have already previously discussed this.

112
00:08:03,720 --> 00:08:05,490
So we are not repeating it over here.

113
00:08:05,490 --> 00:08:10,620
And we were left with finding the time complexity for the backtracking part.

114
00:08:10,650 --> 00:08:15,240
Now we know that there are two to the power n minus one partitions.

115
00:08:15,450 --> 00:08:22,320
And again, each partition in fact represents one of the leaf nodes in this recursion tree over here.

116
00:08:22,320 --> 00:08:30,000
And for each partition we have to build the substrings which is an O of n operation.

117
00:08:30,000 --> 00:08:32,160
Now you can think of it in this manner.

118
00:08:32,160 --> 00:08:36,330
Notice that the maximum depth of this tree is of the order of n.

119
00:08:36,330 --> 00:08:40,200
So through these n steps we are building the partition.

120
00:08:40,200 --> 00:08:43,590
And we have to do this in the worst case for all partitions.

121
00:08:43,590 --> 00:08:47,640
So building the substrings is an O of n operation.

122
00:08:47,640 --> 00:08:53,970
And because we have two to the power n minus one partitions, the time complexity or the worst case

123
00:08:53,970 --> 00:09:01,650
time complexity for the backtracking part is going to be of the order of n into two to the power n.

124
00:09:01,650 --> 00:09:06,720
Now again, two to the power n minus one is written as two to the power n, because we just want to

125
00:09:06,720 --> 00:09:09,750
know what's the order of the time complexity.

126
00:09:09,750 --> 00:09:16,290
So that's why the time complexity of the backtracking part is of the order of n into two to the power

127
00:09:16,290 --> 00:09:23,310
n, and over here the part where we build the DP has a time complexity of the order of n square.

128
00:09:23,370 --> 00:09:29,160
Now between these two n into two to the power n is greater than n square.

129
00:09:29,160 --> 00:09:35,160
That's why we can say that the time complexity of this approach is of the order of n into two to the

130
00:09:35,160 --> 00:09:40,140
power n again, why is n into two to the power n greater than n square?

131
00:09:40,140 --> 00:09:46,140
I can rewrite n square as n into n, so I have n over here and n over here.

132
00:09:46,140 --> 00:09:51,690
And if I were to compare two to the power n and n two to the power n is greater than n.

133
00:09:51,690 --> 00:09:55,890
That's why n into two to the power n is greater than n square.

134
00:09:55,890 --> 00:10:01,770
And hence the time complexity of this solution is of the order of n into two to the power n.