Welcome back.
Let's now make a few interesting observations and use those to develop the intuition required to solve
this question.
Now for this, let's make use of the example which was given to us.
So this was the example that was given.
If a a b a is the input string, then these are the ways of partitioning this string in a way that all
the substrings are palindromes.
Now the first thing to note over here is that we are dealing with substrings and not with subsequences.
So this is an important distinction.
And we have to be careful to correctly recognize what we are dealing with.
Now the second thing that we can note over here is that in the question, it's mentioned that we need
all the ways, all the possible ways of partitioning the string which is given to us.
Now, this is a strong hint that maybe we could use backtracking for solving this question.
Remember in the backtracking section, we had discussed that whenever you need to find all the ways
of doing something, then probably you need to use backtracking.
So to solve this question, there are just two things to consider.
The first thing is that we need to consider all the possible partitionings, and then we need to check
whether the partition or the substring at hand is a palindrome or not.
So let's see how we can use the gap strategy and the backtracking technique to solve this question.
So let's make some space over here.
Now, when it comes to checking whether a particular substring is a palindrome or not, we are very
familiar with how to do this.
So this should be very easy for you because we have already seen this in previous questions.
So let's say the string which is given to us is a a, B, a.
So we will create a 2d dp array.
And then we have columns for each character in the string given to us.
And we have rows as well.
So each character in the string given to us.
And then we would just iterate over this DP array in a diagonal manner or in a length wise manner.
So initially we would fill these cells which represent substrings of length one.
And because a substring of length one is a palindrome, we can just fill these cells with true.
And then we will go over this diagonal.
And whenever we encounter a substring which is a palindrome, we will fill true over here in the DP
table.
Otherwise we will fill false.
So we have already seen this in previous videos.
So let me go ahead and fill the DP table over here.
So we have true false and false.
And then we have false and true.
And finally we have false.
So once we have this DP table let's say we want to know whether a a, b is a palindrome or not.
Now to know this we would just need to check the cell in the DP table which represents this subproblem.
So the indices over here are 012.
So it starts at index zero and goes up to index two.
Now over here we have 0123.
And over here we have 0123.
Now because it starts at index zero we have to take index zero over here.
And it ends at index two.
So we take two over here.
And notice that this row and this column represents this cell over here.
So we just need to go to this cell.
And we see that it's a false over here.
Therefore we know that a a b is not a palindrome.
So this part for solving the question is easy.
Now let's proceed with the first part.
So to ensure that we consider all the possible partitionings, we will use the backtracking technique.
So let's see that in action.
So again let's take a a b a as the string which is given to us.
I will use a pointer to iterate over these indices which represent characters in the string which is
given to us.
So if we consider the index zero and make a partition, that would give us a string a, and if we make
the partition at index one, it would give us a a.
And if we make the partition at index two, it would give us a, a, b.
And over here we would get a a, b a.
Now these two branches, which is a a b and a a b a, will be pruned because these are not palindromes.
And in the question it's mentioned that we should partition the input string only in a manner that all
the substrings are palindromes.
So that's why we can prune these two branches.
And we just have two valid branches.
Now let's go down these branches over here.
So over here this is the scenario where I did the partition in this manner.
So this a is what we have over here.
And then these are the remaining characters.
So this is again index one two and three.
So I will have a pointer.
And using that pointer I will iterate over these values over here.
And my aim is to identify palindromes that start at index one.
And if I find such a palindrome I will go ahead and do a partition over there.
So first I have index one.
And I see that if I do a partition over here then I'm getting a palindrome.
So I go ahead and do this partition.
And the current partition that we are building at this point becomes a comma a.
And then I am left with b.
Now in this same level, let's just think whether there are other possible partitions.
So I could do the partition over here.
But then I will get a B which is not a valid palindrome.
So I will not do a partition over here.
But if I do a partition over here I'll get a b a, which is in fact a valid palindrome.
So this is another branch which can be over here.
So I have a comma a b a.
Now in this branch over here where I have a and a, I did the partition over here.
Right.
So initially I did it over here.
That's how this a got added.
And then I did a partition over here.
Therefore I have a and a.
Now the remaining characters are B and A.
Now one way of doing a partition over here when we consider this substring is in this manner because
B alone is a palindrome.
So let me do that.
So I get a, a and b.
And then the other way is doing the partition over here.
But this branch is pruned because B a is not a palindrome.
Now again let's go down this branch over here.
I'm just left with a.
So I've done a partition over here.
So that's how this A got added.
Then I did a partitioning over here.
So that's how this A got added.
And then I did a partition over here.
So that's how this B got added.
And now I just have one more character in the string which was given to me.
And I can do a partitioning only in one manner.
And this character alone is a valid palindrome.
So let's add that to the current partition that we have been building.
So I get a, A, B and A.
So this is one of the valid ways of partitioning a a b a such that all the substrings are palindromes.
Also notice that this branch no longer goes down because we have already used up all the characters
in the input string.
So this over here is also a valid way of partitioning the input string such that all the substrings
over here are valid palindromes.
Now let's proceed and complete this branch over here.
So this branch represents the case where we did the first partition in this manner.
So we have a A over here.
Now the remaining characters to be considered are B and A.
So I can do a partition in this manner.
And I get B alone over here.
And because B alone is a valid palindrome.
So I will add it to the current partition that I'm building.
So I get a comma b.
And then the other way or other possibility is to do a partition over here.
But then this is pruned because B a is not a valid palindrome.
And then over here in the next level I just have one character remaining.
And that's also added to this partition to get a, B and A.
So this over here is also a valid way of partitioning the input string because all of these are palindromes
and that's it.
So in this manner using backtracking notice that we've been.
Able to get all the valid ways of partitioning the input string, such that all the substrings over
here are palindromes.
So this is the approach that we will use to solve this question.
Now notice over here we hit the base case in this case because after a was added over here in the next
call, the pointer used to iterate over these characters would be pointing at an index which is greater
than the last valid index over here.
And if that happens, then we can just make a copy of this and add it to a results array, which at
the end we will return.
Notice this is the same case over here as well.
So once we have added a b a the pointer would be pointing over here which is over here which is an invalid
place.
So this is 0123.
So after a b was added in the next call the pointer would have a value four.
And that is when we hit the base case and add this to the results array.
That's the case over here as well.
So we have discussed the approach which can be taken to solve this question.
In the next video.
Let's go ahead and write the pseudocode for this approach.