Welcome back.
Let's say the DP table is already filled with either true or false in the cells that represented valid
substrings of the string that is given to us.
Now let's discuss iterating lengthwise through this DP table to identify how many palindromic substrings
can be formed.
Now first let's make a few interesting observations.
The first thing to note over here is that these cells in the DP table are not meaningful because, for
example, let's take this cell over here.
For this cell, the starting index is two and the ending index is equal to one.
And that's not meaningful right.
Because starting index has to be less than or equal to the ending index.
So these cells are not meaningful.
And to identify how many palindromic substrings can be formed or to identify how many times true occurs
in this DP table over here, we do not need to check these invalid cells.
We just need to count the number of times true occurs in the valid cells which have been filled over
here.
And notice that to count this, we do not need to go through each and every cell in a row wise manner,
but rather we could just go diagonally starting with this diagonal over here.
So when we go diagonally, notice that these cells over here represent substrings of length equal to
one, because the starting index and the ending index for these cells are one and the same.
So the length of these substrings is equal to one.
Similarly these substrings over here have a length equal to two because.
Notice over here.
For example, this substring over here starts at index one and goes up to index two.
So there are two characters in this substring.
In a similar manner, the next iteration would represent substrings of length equal to three.
And the next iteration represents substrings of length equal to four.
And then we have length equal to five over here.
And finally this substring over here starts at index zero and goes up to index five.
So the length is equal to six.
So we have seen over here why iterating diagonally makes sense because these over here don't represent
valid substrings.
We will also use iterating diagonally when we discuss the tabulation approach for solving the palindromic
substrings question.
Now that we know that we want to go through over this DP table diagonally iterating in this manner,
let's discuss how this can be achieved in code.
And let's go ahead and write the pseudo code of the approach that can be taken to achieve this.
Now notice that over here the length of the substring is equal to one.
The length of the substring in these cases is equal to two, and it goes on in this manner.
And finally the length of this substring is equal to six.
So if this is the string that is given to us, the length goes from one up to six.
Okay.
So we can say that for L.
Is equal to one up to n, because n in this case is the length of the string which is given to us,
and that's equal to six.
So for L is equal to one up to n.
And then let's find the value of I which represents the row and j which represents the column.
Notice over here for the first diagonal I ranged from values zero up to five.
For the second diagonal.
When length was equal to two, I ranged from the value zero up to four.
So we can make the observation that I is ranging from zero up to n minus L, because in this case n
is equal to six and n minus l is equal to five.
And over here n again is equal to six and length is equal to two.
So n minus l is equal to four.
So I is ranging from zero up to n minus l.
Now having got the value of I we can say that j is equal to I plus l minus one.
Now why is that the case.
Let's just walk through this to understand this.
So initially L is equal to one.
And I is ranging from zero up to five.
So I have zero, one, 234 and five.
These are the values of I.
Now let me find the value of j for each respective value of I and l is equal to one.
So one minus one gives me zero.
So j is just going to equal to I.
So the various values of j in these instances are zero, one, two, three, four and five.
So zero zero gives me this cell one one gives me this cell two two gives me this cell three three gives
me this cell four four gives me this cell.
And finally five five gives me this cell.
Let's take one more example.
Let's say l is equal to two.
And when L is equal to two I ranges from 0 to 4.
So I have zero one, two three and four.
And then j is going to equal I plus l minus one.
Because l is equal to two two minus one is equal to one.
So j is going to equal I plus one.
So when I is equal to zero j will equal one.
When I is equal to one, j will be equal to two.
Similarly over here j is equal to three.
And then we have j is equal to four over here.
And j is equal to five over here.
Now zero comma one gives me this cell one comma two gives me this cell two comma three gives me this
cell three comma four.
Again you have three over here four over here.
So that gives me this cell.
And four comma five gives me this cell.
Notice over here we have successfully iterated in a diagonal manner.
So we can use this approach for iterating over the DP table in a diagonal manner or in a lengthwise
manner.
So for the memoization approach, once we have written the recursive function, and once we have ensured
that we are storing what we are computing, we will first go through all the possible substrings and
fill either true or false in the respective cells that represent the substring at hand.
And then we will use this approach to iterate over the DP table diagonally or in a lengthwise manner
to count the number of times true occurs in the DP table over here, and that would be the answer to
the question.