Let's now do a dry run for the approach that we have discussed in the previous video.
So let's again take the input string as a b, a, a, c.
And we have already discussed that this is going to be our DP table which is a 2D array.
And we have a, b, a, a, c on the columns as well as over here we have a, b, a, C on the rows.
And the indices over here range from zero up to four, which is true for columns and rows.
Now we are going to start iterating over the substrings in a length wise manner.
So we have these cells over here which all represent strings of length one.
And we know that if a string just has one character, these are palindromes.
And because they are palindromes, we will not require any cut.
So we can fill these values over here with zero which represents zero cuts.
Now we proceed to this cell over here, which represents the substring that starts at index zero and
goes up to index one, which is a b.
Now for a b, because a and b are not equal, we will need one cut.
So that's why we can fill the value over here with one.
Now we proceed to this cell, which represents the substring that starts at index one and goes up to
index two, which is b again.
B is not equal to a.
Therefore we would need to do one cut and we can fill one over here.
And then we come to this cell again it starts at index two and goes up to index three.
That's AA.
Now we see that A and A are equal.
These two characters are equal.
And therefore this is a palindrome.
And we do not need any cuts.
And therefore we can fill zero over here.
Then we proceed to this cell over here.
It represents the substring that starts at index three and goes till index four which is A-C.
Now a and c are not equal.
And therefore we will need one cut.
And we can fill one over here.
And we are done with this diagonal.
Now we proceed to these cells over here.
So this cell over here represents the substring that starts at index zero and goes up to index two which
is ABBA.
Now we see that these two are equal, A and A is equal, and the remaining part of ABA after we remove
A and a is also a palindrome.
So over here also we have a palindrome.
Therefore for ABA we will need no cuts because ABA is a palindrome in itself.
So we can fill zero over here.
Now let's proceed to the next cell.
So over here we have the substring that starts at index one and goes up to index three, which is b,
a, a and b and a are not equal.
So let's think of the two steps that we have discussed in the previous video.
First we will have to decide about making one cut.
And then we would have to analyze the subproblems.
So what are the ways in which we can make one cut over here.
So again these are the indices 123 in the string which is given to us.
So b is index one.
This is index two which is a and index three also has an a.
So what are the different ways in which we can make one cut.
So we can have b and a a or B a and a.
Now b over here just b is represented by the substring that starts at index one and goes up to index
one.
So this over here can be represented as one comma one.
And this substring over here is the substring that starts at index two and goes up to index three.
So we can write two comma three over here.
And in a similar manner b a over here.
This starts at index one and goes up to index two.
And this substring over here starts at index three and goes up to index three.
As we have discussed in the previous video, this over here is achieved using one more variable.
So let's call that k.
So over here k has the value one.
And over here k has the value two.
So k ranges from one up to two right.
So from I up to j minus one.
So over here k has the value one.
And over here k has the value two.
And in each of these cases we have to calculate the number of cuts required for these two subproblems
and add one to it.
Because this in fact is a cut which is dividing the problem at hand, which is b a into these two subproblems
in these two ways.
So let's go ahead and take a look at the number of cuts required in these two scenarios.
So over here we have B and this is a palindrome because it has just one character.
So we just need zero cuts for this string over here.
And for this string a because this is a palindrome.
Again we would just need zero cuts.
Therefore DP at I k over here is zero and dp at k plus one.
J is also equal to zero, and the total number of cuts required is zero plus one plus zero.
Now what about this case over here.
Now BA this subproblem over here will require one cut to divide this into two palindromes b and a.
So we will need one cut over here.
And then because this is just one character this substring over here is a palindrome.
So we would need zero cuts over here.
So the total cuts required would be one plus one plus zero.
Because dp at I k in this case is one.
And then we have this one over here.
And then dp at k plus one j in this case is equal to zero.
So we have seen the number of cuts required in these two cases.
Let's also take a look at these values in the DP table that we have.
Now we know that we have already solved problems which are of lower length than three.
So the length of this problem is three.
So we already have the solutions to problems of length one and length two.
And that's the case of these subproblems over here.
So over here this substring which starts at index one and ends at index one is in fact this cell over
here.
Right.
It starts at index one and goes up to index one.
And the value zero is something that we have already computed.
Similarly this subproblem over here, which is the substring that starts at index two and goes till
index three, is this subproblem which is represented by this cell.
So it starts at index two and goes up to index three.
And we already have the value zero which is something that we're using over here.
So we have already calculated it.
Similarly this subproblem which starts at index one and goes up to index two is this cell or represented
by this cell.
And we already have computed it previously.
And this subproblem which starts at index three and goes up to index three is this cell or represented
by this cell.
And it has the value zero which is what we are using over here.
So notice how we are using things that we have previously calculated to find the answer to the problem
at hand, which is the minimum number of cuts required for BA.
Now we know that there are these two possibilities.
So.
So in this case we would need one cut.
And in this case we would need two cuts.
And the minimum between these two is equal to one.
And therefore the solution for this becomes one.
And we can fill that over here.
So the problem which starts at index one and goes up to index three, which is what we have over here
can be solved with just one cut.
So that's what we have found over here.
And we feel that in this cell over here.
Now let's proceed with the next cell.
So over here we have the substring that starts at index two and goes up to index four which is a a c.
Now again we see that a and c are not equal.
Therefore let's think of making one cut.
And the indices over here are two, three and four.
Now the different ways in which we can do one cut are A and a, C and a and c.
Now for this case we would not require any cut for a and for a C we would need one cut.
So the total number of cuts required would be zero plus one plus one.
And over here we do not need a cut for a.
We also do not need a cut for C.
So the total cuts would be zero plus one plus zero.
So over here we need two cuts.
And over here we need just one cut.
And the minimum between these two is equal to one.
And therefore we can fill one over here.
And we are done with this diagonal.
Now let's proceed to the next case which is the substring a b a a now a and a over here are equal.
But when we consider the remaining substring, when we remove these two characters, we have ba, which
is not a palindrome.
Therefore, this substring over here is not a palindrome, and we proceed with our approach.
First we think of making one cut.
Now the different ways in which we can make a cut are a, b a a a, b, a, a, a, b, a, and a.
Now in each of these cases, we will have to find the number of cuts that would be required for the
substrings.
And we already have computed them in the DP table over here.
Because notice that the length of this substring is equal to four.
But the length of the subproblems over here are less than four.
And because we have been iterating lengthwise, we have already calculated these and we already know
how to get these from the DP table.
It's just dp at I k.
That would give us these substrings or these subproblems, and then DP at k plus one j will give us
these subproblems.
And then the number of cuts required would be dp at I k plus one plus dp at k plus one j.
Now let's go ahead and take a look at the number of cuts required for these three cases respectively.
So over here we would need zero plus one plus one cuts because we have to do a cut over here.
And in this case we would need one cut over here and zero cuts over here.
And over here.
We would need zero cuts.
And over here also we would need zero cuts.
So this is equal to two.
This is equal to two.
And this is equal to one.
And the minimum between these three is equal to one.
And that's why we can fill this cell over here with the value one.
And then let's proceed to the next cell.
The problem over here starts at index two and goes up to index four.
That's the substring b a c.
Now we see that b and c are not equal.
Therefore we have to think of making one cut.
Now the different ways in which this can be done is b a a c b a, a c and b a, a and c, and the indices
over here are one, two, three and four.
And let's take a look at the number of cuts that would be required in these three cases.
So over here we need zero cuts.
And over here we would need one cut.
So that's zero plus one plus one.
And in this case we would need one cut.
And over here also we would need one cut.
So that's one plus one plus one.
And over here we would need one cut and zero cuts over here.
So that's one plus one plus zero.
So the minimum among these three is equal to two.
And therefore we can fill two in this cell over here.
So let's do that.
And again in the table we find this using another variable called k.
So this over here represents k is equal to one because k goes from I up to j minus one.
So k is one.
Is this scenario k is equal to two, is this scenario and k is equal to three is this scenario.
And in each of these cases, the value for the number of cuts required for this sub problem would be
given by dp at I k, and the value for the number of cuts required for these sub problems would be given
by dp k plus one j.
And then we're just going to find this for each of these cases.
And then we will find the minimum among these and assign it to the cell at hand.
So this is how we filled two over here.
And the final problem starts at index zero and goes up to index four which is a b a a c.
And this will give us the answer because a b a, a c is the question that was asked of us.
So we have a b a a c, we see that a and c are not equal.
So we proceed and we will make one cut.
Now the different ways of doing this are a, b a, a, c a b a, a c a b a a c and a b a, a and c,
and over here k is equal to zero.
We have k equal to one.
Over here k is equal to two over here, and k is equal to three over here.
And in each of these cases we are going to find dp at I k and dp at k plus one j dp at I k will give
us the number of cuts required for these subproblems, and dp at k plus one j will give us the number
of cuts required for these subproblems over here.
So when k is equal to zero dp at I k and again I is equal to zero and j is equal to four.
So dp at I, k is dp at zero zero, which is equal to zero.
And again we know that for this substring we will just require zero cuts.
And this value over here would be dp at one four because k is equal to zero.
So this is dp at zero plus one which is one and j is four.
So dp at one four.
Is this value over here.
So back will require two cuts.
So the total number of cuts required would be zero plus one plus two.
Similarly over here the number of cuts that would be required is one plus one plus one.
And over here we have zero plus one plus one.
And finally over here we have one plus one plus zero.
And the minimum value among these four values is equal to two.
And therefore we can fill two in the cell over here.
And this is the answer to the question.
So the minimum number of cuts required for a, b, a, a, c such that all the substrings are palindromes
is equal to two.