Hey there and welcome back.
Let's now discuss the tabulation approach by just using a one dimensional array for solving palindrome
partitioning two.
Now, before we start with the approach, let's first build the intuition behind this approach.
So for this let's take an example.
Let's say the string which is given to us is a b a a.
Now the maximum number of cuts that we can do on this string over here, such that every substring is
a substring of length one is equal to three, which would be the case where we make a cut over here,
over here and over here.
So that's three cuts.
And this is the maximum.
All right.
Now we are going to have a pointer.
And with the pointer we are going to iterate over the start value.
So initially start is over here.
And end will be kept over here itself.
So initially start is over here.
And we're going to check whether the string that goes from start to end is a palindrome or not.
And we see that this is not a palindrome.
So we retain the cuts as three itself.
Next we move the start value from here to here.
So initially start was over here.
Now this is going to be moved from here to here.
And we have start over here and end over here.
And we are considering this substring over here which is b a.
Now b a a is also not a palindrome.
Therefore we retain the number of cuts required as three.
Now the number of cuts required will only change when we get a palindrome.
Next we again move the start index from here to here.
And we are considering this substring over here which is a a, and we see that a a is a palindrome.
Now because A is a palindrome, we can achieve a lower number of cuts by doing a cut over here.
Okay.
So doing a cut over here would split this problem into these two subproblems.
So this subproblem over here is the string a b.
And then we have a a over here.
And because A is a palindrome we would need zero cuts for this part.
And the total number of cuts that are required for this string over here would be zero plus one, plus
the number of cuts required for converting this string into substrings where every substring is a palindrome.
So the total number of cuts would be cuts required for the previous part, which is a B plus one, which
is this cut over here, plus zero, which is the number of cuts required for this substring.
And it's zero because this is a palindrome.
Now let's say we know this or the number of cuts required for a b.
And we will soon discuss why we will know this in this approach.
So for now let's say we know this.
That would indicate that the number of cuts required for a, b a is one plus one plus zero, which is
equal to two.
So this is one possibility.
Now let's proceed.
And now start is going to equal end.
Now remember end was over here and start was over here for this case.
Now we are again going to move this pointer and start is also going to equal a.
And end is also equal to a.
So the substring that we are considering is a.
And because a is a palindrome we are going to evaluate the number of cuts required for this case.
So the number of cuts would be the number of cuts required for the previous part which is a b a over
here plus one.
So this one is for this cut over here plus zero.
And we have zero over here.
Because this over here is a palindrome.
Now let's say again we know the number of cuts required for the previous part.
And that's equal to zero because a b a is a palindrome.
So that's why we have zero over here.
And that gives us the total number of cuts required for the string at hand with this approach as zero
plus one plus one which is equal to one.
So that's one over here.
So among three two and one the minimum is equal to one.
And therefore the minimum number of cuts required for partitioning a, b A a into substrings in a way
that every substring is a palindrome is equal to one.
So this is going to be the approach that we will take.
Let's also quickly discuss why we would know the number of cuts required for the previous part over
here and over here.
Now again we have the example a b a a.
Now the way that we would implement this is that we would have a DP array.
And initially we will consider that a is the string which is given to us.
And over here we will fill the minimum cuts required for this substring which is zero.
Then we would consider a b as the string given to us, and the minimum number of cuts required for this
would be filled over here, which is equal to one.
And then we would consider a, b a and then finally a b a.
So that's why at every point we would know the number of cuts required for a substring of lower length.
Now we will see more of this in the next video when we do a dry run of this algorithm.
But over here let's do one more quick observation.
Notice over here that if a b, a A, or the string that we are considering was a palindrome, then we
would directly know that the minimum number of cuts required would be equal to zero.
For example, if the string given to us was a b a a, then we would not need to do a cut.
We would directly know that the number of cuts required would be.
Zero, because we see that these two characters are equal.
And the middle part over here is also a palindrome.
And which would mean that a b a a is a palindrome in itself, and therefore it would just require zero
cuts.
So this is also something that we would incorporate when we write the pseudo code for this approach.
So over here we have developed the intuition.
And we have seen that if we know the minimum cuts required for a smaller problem, we can find the minimum
cuts required for the original problem which is a b a.
In the next video, let's dry run this algorithm to solidify what we have learned over here and build
a good understanding of this approach.