Hey there and welcome back.
In this video, let's do a dry run of the second tabulation approach that we have discussed for solving
palindrome partitioning two.
So for this let's say the input given to us is a b a a, C.
And as we have discussed we will just use a one dimensional DP array.
So initially we will consider only this substring over here which has just one character a.
Now we know that this is a palindrome.
And therefore over here we will fill zero.
So in the DP array at every cell we are going to fill the minimum number of cuts required for the substring
that goes from zero up to index I.
So if I is the index that we are considering, every cell over here will be filled with the minimum
cuts required to partition the string that goes from zero up to index I in a way that every substring
is a palindrome.
So we have seen that over here we will fill the value zero.
Now we will proceed with the next substring which starts at index zero and goes up to index one.
So ab is the substring that we are considering now because a and b are not equal.
So because this is not a palindrome we will consider making one cut.
And again we are doing this because AB is not a palindrome.
So when we move the start index and have it point to this index over here and end was already over here,
we are just considering this substring.
And we see that this is in fact a palindrome.
Therefore, in this case the number of cuts required would be one plus the number of cuts required for
the previous part, which is just a and for a.
We know that we don't need to do any cuts, and we already have that in the DP table over here.
So in this case the number of cuts required is one plus zero which is equal to one.
So we can go ahead and fill one over here.
Notice that initially for string AB the maximum number of cuts is one itself.
And over here we have seen that between 1 and 1 the minimum is also one.
So we go ahead and fill one over here.
Now let's proceed to the next substring which is ab a.
Now the maximum number of cuts over here would be two which is one and two.
But again over here we notice that ab a in itself is a palindrome.
And therefore we would not require any cut for this substring.
And we can go ahead and fill zero over here.
So we have zero over here in the DP table.
And then we proceed to the next substring which is ab a.
Now ab a is not a palindrome.
So the maximum number of cuts that can be done for this substring is three.
So cuts is set initially to the value three.
And then we're going to explore the different possible substrings by moving the start value.
So initially start is over here and end is over here.
And we have seen that this over here is not a palindrome.
So we move start and start comes over here.
So AB A is not a palindrome.
So start has been moved.
And we are considering b a a and b a is also not a palindrome.
Again we move the value of start and we are considering a a and a is in fact a palindrome.
Therefore, the number of cuts required in this scenario is one plus the number of cuts required for
AB, which is the previous part, and for AB.
From our DP table, we know that the number of cuts required is equal to one.
So the number of cuts required in this scenario is one plus one which is equal to two.
Now we proceed.
So again remember at this point start is over here and end is over here.
Now we are again going to move this pointer.
And it's going to point at a.
So the string that we are considering is a.
Now this is a palindrome because it's a substring of length one.
And therefore let's consider the number of cuts required in this scenario.
So the number of cuts required for this scenario would be the number of cuts required for the previous
part, which is AB a plus one plus zero.
Because again we don't need any cuts for this part.
So the total number of cuts required is the number of cuts required for ABBA plus one.
And for ABBA, we know that we don't need to do any cuts.
So this over here becomes zero plus one, which is equal to one now among three, two and one, the
minimum value is one, and therefore the minimum cuts required for AB a a is equal to one.
And we can fill this value over here.
Now let's proceed to the next problem which is a b a a c.
Now we see that this is not a palindrome.
And therefore we initialize cuts to the maximum number of cuts which is equal to four.
So cuts now is equal to four.
And we have seen that a, b, a c is not a palindrome, then we are going to consider back by moving
the start index from here to here and back is also not a palindrome.
Again, we will move the start index and we are considering a a c a a c is also not a palindrome.
So we again move the start index and we are considering a C.
A c is also not a palindrome.
Therefore we will move the start index and we are just considering c and C is a palindrome.
So the number of cuts required in this case would be the number of cuts required for the previous part,
which is a, b a, a plus one, and for a b a a.
From the DP table we know that we just need one cut.
So this over here simplifies to one plus one which is equal to two.
And between 4 and 2 two is the minimum value.
And therefore we feel that over here and we are done filling our DP table.
And this over here gives us the answer.
Or the last value in the DP table gives us the answer.
Because notice over here this represents the minimum cuts required for the string that starts at index
zero and goes up to this index over here.
And that's 0123 and four.
So this over here represents the number of cuts required for the string that goes from zero to index
four, which is actually the problem given to us.
So the answer to this question is equal to two.
And I'm sure this dry run has helped solidify learning how this algorithm works.