Let's now get into the code for solving the palindromic substrings question.
So over here we are going to implement the memoization approach.
And notice we are given this function.
And to this function the string S is given.
Now let's say n is the length of the given string.
And let's create a DP table.
So we would need a 2d dp table which will have n rows and n columns.
Okay.
So let's go ahead and implement that.
Okay.
And we would also need n columns.
And what we will do is we will fill every cell in this DP table with the value minus one.
Okay.
And this is going to be a recursive solution.
And we are going to use a helper function.
Let me just call it helper itself.
To this function we will be passing two indices which represent the start index and the end index okay.
And a combination of I and j will give us a substring.
In this manner we will go through all the relevant substrings.
And using this helper function, wherever we find a substring which is a palindrome, we will fill the
value true in the DP table.
Okay.
So let's write the details of this helper function later.
And we would have to call this helper function for the first time.
And when we do that we will pass the indices zero and n minus one to it okay.
Because that's the first index and the last index of the given string.
Once we are done with this, we would just have to iterate through the DP table in a diagonal or length
wise manner, as we have discussed in the previous video, and we would just have to count the number
of times true occurs.
Okay, let's have a variable race where we are going to store this particular count.
And finally we will be just returning this.
Okay.
Now let's go ahead and write the code for iterating through the DP table in a diagonal manner.
It's pretty straightforward.
So we'll have two for loops.
And over here I will say for let L is equal to one L less than or equal to n l plus plus.
Because l or length can take the values from one up to n, and for each value of L will have another
variable.
Let us call it I, and I will take the values from zero up to n minus n, so I less than equal to n
minus l okay.
And I plus plus.
All right.
So we are getting a combination of L and I.
And for each of these combinations we will take J as I plus L minus one.
And we have discussed the logic for this in detail in the previous video okay.
And each combination of I and J will give us one of the cells when we are iterating through the DP table
in a length wise manner or diagonally, and we will just check if dp at I, j is equal to true, and
if it is equal to true, then we will increment rest.
And that's it.
Now all that remains is to complete the helper function.
So let's go ahead and do that okay.
So in the helper function over here we are going to write the base case as well as the recursive case.
Okay.
Now, what would be the base case?
The base case is the scenario where I and J are equal okay.
So if I is equal to j then we can just say that dp at I j is equal to true okay.
Because we are just dealing with a substring of length one.
And we know that a string of length one is in fact a palindrome.
And if we get true over here, we will just return dp at ij.
Okay.
Now after the base case, before we go ahead and do the recursive case and do these computations over
here, we are going to check whether we have already computed and stored this in depth ij.
And for that we will check whether dp at ij is not equal to minus one, because if it's not equal to
minus one, the reason for it not being minus one is that we have computed and stored it in dp at ij
because node is over here.
Initially we had filled every cell in the DP table with the value minus one.
So if dp at ij is not equal to minus one, then we don't need to do any computations, but rather we
will just return dp at ij okay.
And then we proceed.
So if this is not the case then we proceed and do computations.
And then we will store the respective value that we get at dp at ij and then return dp at ij.
So that's what we are going to do over here.
So let's go ahead and continue with the code.
So we are going to check whether s at I is equal to s at J.
Okay.
So again this is an if statement.
So if these two characters are equal and if either this substring that we are considering just has two
characters.
And for checking that we can just check whether j is equal to I plus one, because if j is equal to
I plus one, it means that the substring just has two characters.
And over here, if this is true, it means that those two characters are equal and therefore we are
dealing with a palindrome.
Okay, so either this has to be true or if these two characters are equal.
And then once you remove those two characters, whatever you are left with, that also should be a palindrome
for the substring that starts at I and goes up to j to be a palindrome, and to check that we will just
recursively call the same helper function which we are writing over here, and we will pass I plus one
to it and j minus one to it.
So basically we are just removing these two characters, and we are checking whether the remaining substring
is a palindrome or not.
Okay.
So if this is true and if either of these is true then we will just say depee at I j is equal to true.
Okay.
And I think I've missed a bracket over here.
So let's correct that.
And if this is not the case then we will just say dp at I j is equal to false.
Okay.
Now there's one more thing that we have to do over here.
We have to check the two cases where we are only moving one index at a time okay.
So in this case let's just move I.
So this would be helper I plus one J.
And over here we will have the case where we are only moving J.
Okay.
It would be I and j minus one.
So we have to check these two scenarios as well to see whether we are getting palindromes or not.
All right.
So that's it.
Now this should take care of it.
Now I see there is a error over here.
So I think I've made a mistake.
Let me quickly check that okay.
So I see there's a missing bracket over here.
And that's it.
Now let's go ahead and run this code and see if it's passing all the test cases.
And it's working.
So this is the memoization approach for solving the palindromic substrings question.