1
00:00:00,420 --> 00:00:01,500
Welcome back.

2
00:00:01,530 --> 00:00:09,480
Let's now make a few interesting observations and use those to develop the intuition required to solve

3
00:00:09,480 --> 00:00:10,350
this question.

4
00:00:10,380 --> 00:00:14,820
Now for this, let's make use of the example which was given to us.

5
00:00:14,820 --> 00:00:17,100
So this was the example that was given.

6
00:00:17,100 --> 00:00:24,870
If a a b a is the input string, then these are the ways of partitioning this string in a way that all

7
00:00:24,870 --> 00:00:27,060
the substrings are palindromes.

8
00:00:27,330 --> 00:00:33,900
Now the first thing to note over here is that we are dealing with substrings and not with subsequences.

9
00:00:33,900 --> 00:00:36,180
So this is an important distinction.

10
00:00:36,180 --> 00:00:41,850
And we have to be careful to correctly recognize what we are dealing with.

11
00:00:42,120 --> 00:00:48,360
Now the second thing that we can note over here is that in the question, it's mentioned that we need

12
00:00:48,360 --> 00:00:54,300
all the ways, all the possible ways of partitioning the string which is given to us.

13
00:00:54,300 --> 00:01:00,780
Now, this is a strong hint that maybe we could use backtracking for solving this question.

14
00:01:00,780 --> 00:01:06,870
Remember in the backtracking section, we had discussed that whenever you need to find all the ways

15
00:01:06,870 --> 00:01:11,070
of doing something, then probably you need to use backtracking.

16
00:01:11,070 --> 00:01:15,780
So to solve this question, there are just two things to consider.

17
00:01:16,420 --> 00:01:23,710
The first thing is that we need to consider all the possible partitionings, and then we need to check

18
00:01:23,710 --> 00:01:28,780
whether the partition or the substring at hand is a palindrome or not.

19
00:01:29,050 --> 00:01:36,250
So let's see how we can use the gap strategy and the backtracking technique to solve this question.

20
00:01:37,010 --> 00:01:39,050
So let's make some space over here.

21
00:01:39,050 --> 00:01:45,890
Now, when it comes to checking whether a particular substring is a palindrome or not, we are very

22
00:01:45,890 --> 00:01:47,510
familiar with how to do this.

23
00:01:47,510 --> 00:01:52,850
So this should be very easy for you because we have already seen this in previous questions.

24
00:01:52,850 --> 00:01:56,810
So let's say the string which is given to us is a a, B, a.

25
00:01:56,840 --> 00:01:59,840
So we will create a 2d dp array.

26
00:01:59,960 --> 00:02:04,100
And then we have columns for each character in the string given to us.

27
00:02:04,100 --> 00:02:05,780
And we have rows as well.

28
00:02:05,780 --> 00:02:08,510
So each character in the string given to us.

29
00:02:08,510 --> 00:02:15,290
And then we would just iterate over this DP array in a diagonal manner or in a length wise manner.

30
00:02:15,290 --> 00:02:20,870
So initially we would fill these cells which represent substrings of length one.

31
00:02:20,870 --> 00:02:27,200
And because a substring of length one is a palindrome, we can just fill these cells with true.

32
00:02:27,200 --> 00:02:29,990
And then we will go over this diagonal.

33
00:02:29,990 --> 00:02:35,540
And whenever we encounter a substring which is a palindrome, we will fill true over here in the DP

34
00:02:35,540 --> 00:02:36,110
table.

35
00:02:36,110 --> 00:02:37,910
Otherwise we will fill false.

36
00:02:37,910 --> 00:02:40,370
So we have already seen this in previous videos.

37
00:02:40,370 --> 00:02:43,220
So let me go ahead and fill the DP table over here.

38
00:02:43,220 --> 00:02:45,980
So we have true false and false.

39
00:02:46,340 --> 00:02:48,590
And then we have false and true.

40
00:02:48,590 --> 00:02:50,390
And finally we have false.

41
00:02:50,660 --> 00:02:58,670
So once we have this DP table let's say we want to know whether a a, b is a palindrome or not.

42
00:02:59,000 --> 00:03:07,790
Now to know this we would just need to check the cell in the DP table which represents this subproblem.

43
00:03:07,790 --> 00:03:11,060
So the indices over here are 012.

44
00:03:11,090 --> 00:03:14,960
So it starts at index zero and goes up to index two.

45
00:03:14,990 --> 00:03:17,720
Now over here we have 0123.

46
00:03:17,720 --> 00:03:20,300
And over here we have 0123.

47
00:03:20,300 --> 00:03:24,740
Now because it starts at index zero we have to take index zero over here.

48
00:03:24,740 --> 00:03:26,780
And it ends at index two.

49
00:03:26,810 --> 00:03:28,310
So we take two over here.

50
00:03:28,310 --> 00:03:34,100
And notice that this row and this column represents this cell over here.

51
00:03:34,100 --> 00:03:36,770
So we just need to go to this cell.

52
00:03:36,770 --> 00:03:38,930
And we see that it's a false over here.

53
00:03:38,930 --> 00:03:43,070
Therefore we know that a a b is not a palindrome.

54
00:03:43,070 --> 00:03:47,300
So this part for solving the question is easy.

55
00:03:47,330 --> 00:03:49,850
Now let's proceed with the first part.

56
00:03:50,580 --> 00:03:58,230
So to ensure that we consider all the possible partitionings, we will use the backtracking technique.

57
00:03:58,230 --> 00:04:00,060
So let's see that in action.

58
00:04:00,060 --> 00:04:04,590
So again let's take a a b a as the string which is given to us.

59
00:04:04,890 --> 00:04:12,180
I will use a pointer to iterate over these indices which represent characters in the string which is

60
00:04:12,180 --> 00:04:12,930
given to us.

61
00:04:12,930 --> 00:04:22,020
So if we consider the index zero and make a partition, that would give us a string a, and if we make

62
00:04:22,020 --> 00:04:25,800
the partition at index one, it would give us a a.

63
00:04:25,800 --> 00:04:30,360
And if we make the partition at index two, it would give us a, a, b.

64
00:04:30,360 --> 00:04:33,000
And over here we would get a a, b a.

65
00:04:33,120 --> 00:04:41,340
Now these two branches, which is a a b and a a b a, will be pruned because these are not palindromes.

66
00:04:41,340 --> 00:04:48,480
And in the question it's mentioned that we should partition the input string only in a manner that all

67
00:04:48,480 --> 00:04:50,580
the substrings are palindromes.

68
00:04:50,580 --> 00:04:53,370
So that's why we can prune these two branches.

69
00:04:53,370 --> 00:04:56,070
And we just have two valid branches.

70
00:04:56,070 --> 00:04:58,560
Now let's go down these branches over here.

71
00:04:58,560 --> 00:05:03,540
So over here this is the scenario where I did the partition in this manner.

72
00:05:03,540 --> 00:05:05,700
So this a is what we have over here.

73
00:05:05,700 --> 00:05:08,310
And then these are the remaining characters.

74
00:05:08,310 --> 00:05:11,970
So this is again index one two and three.

75
00:05:11,970 --> 00:05:13,890
So I will have a pointer.

76
00:05:13,890 --> 00:05:18,270
And using that pointer I will iterate over these values over here.

77
00:05:18,270 --> 00:05:23,790
And my aim is to identify palindromes that start at index one.

78
00:05:23,790 --> 00:05:28,350
And if I find such a palindrome I will go ahead and do a partition over there.

79
00:05:28,350 --> 00:05:30,390
So first I have index one.

80
00:05:30,390 --> 00:05:35,340
And I see that if I do a partition over here then I'm getting a palindrome.

81
00:05:35,340 --> 00:05:37,560
So I go ahead and do this partition.

82
00:05:37,560 --> 00:05:42,600
And the current partition that we are building at this point becomes a comma a.

83
00:05:42,600 --> 00:05:44,670
And then I am left with b.

84
00:05:44,880 --> 00:05:50,190
Now in this same level, let's just think whether there are other possible partitions.

85
00:05:50,190 --> 00:05:52,320
So I could do the partition over here.

86
00:05:52,320 --> 00:05:56,430
But then I will get a B which is not a valid palindrome.

87
00:05:56,430 --> 00:05:59,160
So I will not do a partition over here.

88
00:05:59,160 --> 00:06:05,010
But if I do a partition over here I'll get a b a, which is in fact a valid palindrome.

89
00:06:05,010 --> 00:06:08,280
So this is another branch which can be over here.

90
00:06:08,280 --> 00:06:11,460
So I have a comma a b a.

91
00:06:11,670 --> 00:06:17,400
Now in this branch over here where I have a and a, I did the partition over here.

92
00:06:17,400 --> 00:06:17,700
Right.

93
00:06:17,700 --> 00:06:19,230
So initially I did it over here.

94
00:06:19,230 --> 00:06:20,700
That's how this a got added.

95
00:06:20,700 --> 00:06:22,770
And then I did a partition over here.

96
00:06:22,770 --> 00:06:24,840
Therefore I have a and a.

97
00:06:24,840 --> 00:06:28,200
Now the remaining characters are B and A.

98
00:06:28,380 --> 00:06:35,460
Now one way of doing a partition over here when we consider this substring is in this manner because

99
00:06:35,490 --> 00:06:37,110
B alone is a palindrome.

100
00:06:37,110 --> 00:06:38,400
So let me do that.

101
00:06:38,400 --> 00:06:40,710
So I get a, a and b.

102
00:06:40,710 --> 00:06:43,800
And then the other way is doing the partition over here.

103
00:06:43,800 --> 00:06:48,210
But this branch is pruned because B a is not a palindrome.

104
00:06:48,600 --> 00:06:51,210
Now again let's go down this branch over here.

105
00:06:51,210 --> 00:06:53,010
I'm just left with a.

106
00:06:53,040 --> 00:06:55,290
So I've done a partition over here.

107
00:06:55,290 --> 00:06:57,000
So that's how this A got added.

108
00:06:57,000 --> 00:06:59,340
Then I did a partitioning over here.

109
00:06:59,340 --> 00:07:01,200
So that's how this A got added.

110
00:07:01,200 --> 00:07:03,120
And then I did a partition over here.

111
00:07:03,120 --> 00:07:04,830
So that's how this B got added.

112
00:07:04,830 --> 00:07:09,600
And now I just have one more character in the string which was given to me.

113
00:07:09,600 --> 00:07:13,050
And I can do a partitioning only in one manner.

114
00:07:13,050 --> 00:07:16,530
And this character alone is a valid palindrome.

115
00:07:16,530 --> 00:07:20,670
So let's add that to the current partition that we have been building.

116
00:07:20,670 --> 00:07:24,030
So I get a, A, B and A.

117
00:07:24,690 --> 00:07:32,100
So this is one of the valid ways of partitioning a a b a such that all the substrings are palindromes.

118
00:07:32,100 --> 00:07:38,760
Also notice that this branch no longer goes down because we have already used up all the characters

119
00:07:38,760 --> 00:07:39,780
in the input string.

120
00:07:39,780 --> 00:07:46,650
So this over here is also a valid way of partitioning the input string such that all the substrings

121
00:07:46,650 --> 00:07:49,080
over here are valid palindromes.

122
00:07:49,080 --> 00:07:52,350
Now let's proceed and complete this branch over here.

123
00:07:52,350 --> 00:07:58,380
So this branch represents the case where we did the first partition in this manner.

124
00:07:58,380 --> 00:07:59,940
So we have a A over here.

125
00:07:59,970 --> 00:08:03,930
Now the remaining characters to be considered are B and A.

126
00:08:03,930 --> 00:08:06,840
So I can do a partition in this manner.

127
00:08:06,840 --> 00:08:09,060
And I get B alone over here.

128
00:08:09,060 --> 00:08:12,240
And because B alone is a valid palindrome.

129
00:08:12,240 --> 00:08:15,450
So I will add it to the current partition that I'm building.

130
00:08:15,450 --> 00:08:17,760
So I get a comma b.

131
00:08:17,880 --> 00:08:22,620
And then the other way or other possibility is to do a partition over here.

132
00:08:22,620 --> 00:08:27,510
But then this is pruned because B a is not a valid palindrome.

133
00:08:27,510 --> 00:08:32,580
And then over here in the next level I just have one character remaining.

134
00:08:32,580 --> 00:08:36,690
And that's also added to this partition to get a, B and A.

135
00:08:36,690 --> 00:08:44,310
So this over here is also a valid way of partitioning the input string because all of these are palindromes

136
00:08:44,640 --> 00:08:45,480
and that's it.

137
00:08:45,480 --> 00:08:49,950
So in this manner using backtracking notice that we've been.

138
00:08:50,070 --> 00:08:56,340
Able to get all the valid ways of partitioning the input string, such that all the substrings over

139
00:08:56,340 --> 00:08:57,930
here are palindromes.

140
00:08:57,930 --> 00:09:01,470
So this is the approach that we will use to solve this question.

141
00:09:01,500 --> 00:09:08,730
Now notice over here we hit the base case in this case because after a was added over here in the next

142
00:09:08,730 --> 00:09:15,450
call, the pointer used to iterate over these characters would be pointing at an index which is greater

143
00:09:15,450 --> 00:09:17,520
than the last valid index over here.

144
00:09:17,520 --> 00:09:24,060
And if that happens, then we can just make a copy of this and add it to a results array, which at

145
00:09:24,060 --> 00:09:25,410
the end we will return.

146
00:09:25,440 --> 00:09:28,620
Notice this is the same case over here as well.

147
00:09:28,620 --> 00:09:36,090
So once we have added a b a the pointer would be pointing over here which is over here which is an invalid

148
00:09:36,090 --> 00:09:36,570
place.

149
00:09:36,570 --> 00:09:38,850
So this is 0123.

150
00:09:38,850 --> 00:09:43,950
So after a b was added in the next call the pointer would have a value four.

151
00:09:43,950 --> 00:09:49,380
And that is when we hit the base case and add this to the results array.

152
00:09:49,530 --> 00:09:51,360
That's the case over here as well.

153
00:09:51,360 --> 00:09:55,560
So we have discussed the approach which can be taken to solve this question.

154
00:09:55,560 --> 00:09:56,820
In the next video.

155
00:09:56,820 --> 00:10:00,180
Let's go ahead and write the pseudocode for this approach.