Welcome back.
Let's now get into the code and implement the tabulation approach for solving the palindromic substrings
question.
So we have this function over here count substrings.
And to this function we are given this string over here.
Now let's say n is the length of the given string.
So let n is equal to s dot length okay.
And finally again we have to count the number of palindromic substrings.
And for that we would need a variable.
And let me just call it rest.
And let's initialize this to be equal to zero.
And we'll keep counting the number of substrings which are palindromes.
And finally we will just return s.
Okay.
Now to continue let's create a DP table which is going to be a 2D array having n rows and n columns.
So let's say net dp is equal to array dot from and we can write array n over here.
R a n.
Okay, now what we will do is we will fill every cell in this depee table with the value false.
Okay, let's proceed and iterate over the cells in this DP table in a lengthwise manner or in a diagonal
manner.
And for this we can just use the nested for loop method that we have discussed.
So I can say for let L is equal to one l less than equal to n l plus plus because L stands for length
and the length goes from one up to n, and for each value of l, I will have another variable I.
So for let I is equal to zero, I less than or equal to n minus l I plus plus okay.
And for each combination of I and l we will have another variable j which is going to equal I plus l
minus one.
And we have discussed this in detail in the previous video.
Now whenever we get a combination of I and J over here, we are actually going through a cell on a particular
diagonal, or we are iterating through the DP table in a diagonal manner.
Now what we are going to do is first we are going to check if I is equal to J, because if these two
are equal, then we are just dealing with the substring which has one character.
And we know that a single character substring is always a palindrome.
So in this case I can say dp at I j is equal to true okay.
And whenever we will set dp at ij to be true, we will also increment rest because that's what we will
finally return over here okay.
So we will return rest finally over here.
Okay, I've already written that.
So let's remove that and probably let's reduce the space over here.
All right.
So over here we have set depee at IJ to be true.
And therefore let's increment this.
All right, and let's proceed.
Now, if these two are not equal, then we will go ahead and check if s at I is equal to s at j.
Okay.
So else if s at I is equal to s at j.
Now if these two characters are equal, then for the substring that we are considering to be a palindrome,
we would either have to be considering a substring of length two okay, which can be checked by checking
whether j is equal to I plus one, or if that is not the case, then depee at I plus one j minus one
also has to be a palindrome.
And again what is it that we are doing over here?
Let me quickly write it and explain it one more time.
So let's say we have I over here and then we have a few more characters okay.
And let's say we have J over here.
Now in this case we are seeing that's at I and S at J are equal.
So whatever character is over here is equal to the character that we have over here.
Now if these two characters are equal for this complete substring to be a palindrome, whatever is in
between these characters also has to be a palindrome.
Right.
And this index over here would be I plus one.
And this index over here would be j minus one.
Okay.
And because we are iterating lengthwise and notice that the length of this substring over here which
starts at index I plus one and goes up to j minus one, is lower than the length of this complete substring,
which starts at index I and goes up to index j.
Therefore, and because we are iterating lengthwise, we would already have calculated this before we
come and try to calculate this.
So that is why we can just directly refer to dp at I plus one j minus one to check whether this substring
over here, which is the substring that starts at index I plus one and goes up to index j minus one
is a palindrome or not.
Okay.
So if these two characters are equal, either we should be dealing with a substring that just has two
characters, or the substring which is in between I and j should be a palindrome.
So if either of these is true, and if this is true, then we can set dp at I j to be equal to two.
Okay.
And whenever we set depee at IJ to be true, we have to increment rest.
So rest plus is equal to one.
And if these two are not equal then we will just say dp ij.
Is equal to false.
And again we can avoid this also because we have already said every cell in the DB table to be false.
But okay, you can write it as well.
It does not matter.
Okay.
Again it means that it's not a palindrome and that's it.
So what we have done over here is we have created this DB table, and we have iterated through the cells
in the DB table in a length wise manner.
And wherever we found a substring that is a palindrome, we have said depth ij to be equal to true.
And whenever we did that, we incremented this and therefore rest now has the count of palindromic substrings
and we are returning it over here.
So this is the tabulation approach for solving this question.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.
So this is the tabulation approach for solving the palindromic substrings question.