Hey there and welcome back.
So we are done with the memoization approach for solving the palindromic substrings question.
And we have got a solution with an O of n square time complexity and an O of n square space complexity.
Let's now take a look at the tabulation approach for solving this question.
To discuss this approach, let's say this is the string that is given to us.
That's p q p r p s.
And we will need a DP table over here.
And again we have columns for each of the indices in the string that is given to us.
And we have rows also for each of the indices in the string that is given to us.
Now to come up with the tabulation approach is going to be very easy because we know already how to
iterate diagonally.
So what we need to do is we need to go through each cell in this DP table over here, which represents
a valid substring.
And we need to check whether it is a palindrome or not.
And if it is a palindrome, we need to fill true in that particular cell.
And if not we need to fill false in that particular cell.
So let's just trace how the algorithm would do that.
So initially we will iterate through these cells over here.
And as we have discussed these cells represent substrings of length equal to one.
Now if a substring has just one character we know that it is a palindrome.
And therefore in all of these cells over here we will fill true.
So let's go ahead and do that.
So we have true in all of these cells.
Now we proceed to the scenario where length is equal to two.
And if a substring has just two characters we just need to check whether the character at index I and
the character at index j are equal or not.
So if they are equal, then we know that we have a palindrome and we can fill true in that particular
cell.
And otherwise we will fill false in the particular cell at hand.
So let's go ahead and do that for this example.
So over here we have p and q.
They are not equal.
So we can fill false over here.
And over here we have Q and P and these are not equal.
So we can again fill false.
Over here we have p and r.
These are not equal.
So we can fill false over here.
And then we have r over here.
And we have P over here.
These are not equal.
So we can fill false over here.
And then we have P over here.
And we have s over here.
These are not equal.
So we fill false over here as well.
Now we proceed to the next iteration which is through these cells over here.
And for these cases we have substrings of length equal to three.
Now if we have a substring of length equal to three we need to first check whether character at index
I is equal to the character at index j.
So this is the starting index and this is the ending index.
And if these are equal then we also need to check the substring that starts at index I plus one and
ends at j minus one to know whether this substring over here that starts at index I and goes till index
j is a palindrome or not.
Now the good thing is that because the length of this substring over here is less than the length of
the substring that goes from I to j, we already have computed this because we were iterating length
wise.
So over here we already have the answers to all the substrings of length one, and we already have the
answers to all the substrings of length two, which means that all the substrings of lower length are
already computed, and we already have filled either true or false for those scenarios in the DP table
over here.
So let's proceed and trace the algorithm.
So over here we have p and we have p itself at index two.
So these two are equal.
And therefore we just need to go ahead and check the substring which starts at index I plus one and
goes till index j minus one.
So I plus one is equal to one and j minus one is two minus one which is one.
Now we know that a substring of length one is a palindrome.
But then let's take a look at how the algorithm solves this.
So the algorithm goes and checks dp at I plus one j minus one which is this over here.
And over here we have already filled through and we can just take this value and fill it over here.
So we get true over here as well.
Now we proceed to the next cell.
So we have Q over here and R.
Now these are not equal.
Therefore we can fill false over here.
And then over here we have p and we have p.
These are equal.
Therefore we just take this value and fill it over here which is d p I plus one j minus one.
So we have true over here.
And then over here we have r and we have s.
These two are not equal.
So we can fill false over here.
So we are done with this iteration.
Now let's proceed to the case where length is equal to four.
Again we check the characters at index zero and three for this cell.
And they are not equal.
So we can fill false over here.
And for the next cell over here we have Q and we have P.
These are not equal.
So we can fill false over here as well.
Over here we have p and we have s.
These are not equal.
So we can fill false over here as well.
So we are done with this iteration.
We proceed to the next iteration.
So over here notice we have p and we have p.
So these two are equal.
Therefore we need to check d p I plus one j minus one which is this value over here which is already
computed because the length of the substring that starts at I plus one and ends at j minus one, is
lesser than the length of the substring that starts at I and goes till j.
And because we've been iterating length wise, we have already calculated this, and we have stored
false over here.
And because these two are equal we need to check this substring.
And this is false.
So we can just take it and fill it over here.
So we have false over here.
And then over here we have Q and S.
They are not equal.
Therefore we can fill false over here as well.
And then finally we come to this string.
So over here we have P and over here we have s.
They are not equal.
So we can fill false over here as well.
And in this manner we have completed iterating length wise and filling the cells in this DP table over
here which represented valid substrings.
Now to identify the number of palindromic substrings we just need a count variable.
And whenever we are filling true in this table over here we would increment that count variable.
So in that way we can identify the number of palindromic substrings.
And finally we can return this count variable.
So this is the tabulation approach for solving the palindromic substrings question.