Welcome back.
Let's now get into the code and solve the longest palindromic subsequence question.
So we are given the string over here.
And let's say n is the length of the string okay.
And let's create a DP array which will have n rows and n columns.
So I can say let dp is equal to array dot from length n okay.
And we also need n columns.
Now what we will do is we will fill every cell in this dp array with the value zero okay.
Now what we have to do is as we have discussed in the previous video, we have to iterate lengthwise
through this DP array okay.
And again we know how to do that.
And once we do that ultimately we will get the answer at DP at zero n minus one.
And we have discussed this in the previous video and we would be returning that.
So this is the approach that we are going to take and to iterate lengthwise through the cells in the
DP array.
We already know how to do that.
We have written it many times.
So we are going to have this nested for loop.
So for let L is equal to one l less than equal to n l plus plus okay.
Because l or length takes the values from one up to n, and for each value of l, we will have I, which
will take the values from zero up to n minus l.
So I can say I less than equal to n minus l I plus plus okay.
And for each combination of I and l, j would be equal to I plus l minus one.
All right.
Now every ij combination gives us a cell in the DP table.
And using this nested for loop structure we are iterating lengthwise or diagonally through the DP table.
And over here first we are going to check whether I is equal to j because if these two are equal, we
are just dealing with the substring of one character.
And such a substring is a palindrome.
And we can just say that the length of this particular substring, or the length of the longest palindromic
subsequence of this particular substring, which just has one character, is equal to one.
So here we'll set dp at ij is equal to one.
Now if this is not the case, we will check whether s at I is equal to s at j okay.
And if these two are equal then as we have discussed in the previous video, we can set dp at ij to
be equal to two plus dp at I plus one j minus one.
Okay.
Else if these two characters are not equal, we would need to take a look at DP at I plus one j and
dp at I j minus one.
So we are only moving one pointer okay or one index and again in the DP table this would be the left
and the bottom element of the cell that we are considering.
So we have to take a look at these two cells.
And because we were iterating lengthwise the length from I to J as you can see, would be greater than
the length from I plus one to j or I to j minus one.
So these two will be values that we have already calculated, and we just need to find the maximum between
these two.
So I can say math dot max between these two okay.
So that's what we will assign to dp at ij.
So dp at ij is equal to math dot max between this and this okay.
And that's it.
So this should solve this question.
And finally we have to return the answer.
And we have already returned the return statement over here.
Return DP at zero n minus one.
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.