Welcome back.
Now let's discuss how we can solve this question.
As you may have felt, this question is pretty similar to the palindromic substrings question that we
have previously discussed.
But before we go ahead and discuss the complete approach, first let's try to think how this question
is different, or in what manners we would need to tweak the approach that we came up with for the palindromic
substrings question, so that we can relate to that question, and then we can easily solve this question
as well as retain what we are learning over here.
Now, we could first try the recursive approach and then memorize it and then come to the tabulation
approach for solving this question.
But because we are already aware of this pattern, let's start with the tabulation approach right away
okay.
So let's get started.
Now in the palindromic substrings question, this was the DP table that we had for the string p q p
r p s.
So if this is the string given to us, this is how we went ahead and formed a DP table.
And then we iterated lengthwise and fill these values with either true or false.
And we solved that question okay.
So in the palindromic substrings question we filled either true or false in each of these cells.
But in this question we will not be able to solve it by just filling the cells with true or false,
especially because we are asked to identify the length of the longest palindromic subsequence.
So what we would need to do is we would need to fill each cell with the longest palindromic subsequence
that can be formed for the substring which is represented by a particular cell.
Okay.
Now let's go ahead and see how we can solve this question.
And for this, or to form the intuition required for solving this question before we go ahead and iterate
over the cells in the table and solve it, let's take a few examples to make a few observations.
So if the string which is given to us where a b c b d a.
Now in this case we would see that this a and this a is equal.
So the first and the last characters are equal.
And if these two are equal, then the longest palindromic subsequence that we can form from this complete
string would be two, because we have one character over here and one character over here.
And again these would be included in the longest palindromic subsequence that we can form from this
string.
So again these two will be included.
So that's why the length of the longest palindromic subsequence that we can form from this string would
be two plus the length of the longest palindromic subsequence that we can get from this substring.
Okay.
And again I'm just denoting this as l.
So if this is L okay.
Then the length of the longest palindromic subsequence that we can form from this string over here would
be two plus l okay.
And again why is this two over here.
Because we have one character over here and one character over here.
So l notice is being increased by two.
Okay.
Now let's take another example.
If the string which we are dealing with is b c b d.
And again that's this string over here.
So if this is the string that we are dealing with we would see that the first and the last characters
are not equal.
And if that is the case then the longest palindromic subsequence that we are going to form from this
string will either not include this character or not include this character.
So what we will do is we will move only one pointer at a time.
So when we move this pointer we get b c b okay.
We are moving this pointer to over here and we'll get BCB.
And if we move this pointer we will get CBD okay.
And then we will try to find the longest palindromic subsequence that we can form in these two scenarios.
So we'll get two numbers.
And then we will take the maximum of these two as the longest palindromic subsequence that we can form
from this string over here okay.
And in this case we can see that for this substring we can form a palindromic subsequence of length
three.
And in this case we are just able to form a palindromic subsequence of length one.
So the greater value between these two is going to be equal to three.
So for this string we will be able to form a palindromic subsequence of length three.
And then the answer for this complete string would be three plus two which is equal to five.
So this is the approach that we will use to solve this question.
Now again remember we will fill each cell in the DP table with the length of the longest palindromic
subsequence that can be formed from the substring which the cell represents okay.
So for.
Example, this cell over here represents the substring that starts at index one and goes up to index
four.
So that's q p r p okay.
So that's q p r p.
And over here in this cell we will fill the length of the longest palindromic subsequence that can be
formed from this substring over here which would be three which is p r p.
Okay.
So we have understood the approach that we will be taking to solve this question.
Now again one more point to remember at this point when we are trying to find the length of the longest
palindromic subsequence that we can form from this string, notice it's being reduced to two subproblems
which are of lower length, so the length of this substring is equal to four, and the length of these
two substrings are three and three respectively.
And because we are going to iterate over these cells in the DP table over here, length wise, we would
already have the answers to these two problems.
So that's why we can use the answers to the previous subproblems, which we would have already computed
to find the answer for this problem over here.
Okay.
And that's the beauty of length wise iteration.
So let's go ahead and see how this pans out.
And let's just do a dry run of the algorithm.
Now we are taking the string which is given to us as p q p r p s.
Okay.
So first we're going to iterate over these cells which represent length equal to one.
So at this point we would see that the two characters are equal okay.
And we are just dealing with substrings of length one.
So we would just fill one in each of these cases.
Now why is that the case.
That's because for example this cell over here represents the substring that starts at index two and
goes up to index two which is just p.
And if you have a string of length one, the character itself is a palindrome and the length is just
one.
Okay.
So that's why we fill one over here.
Now we move to this diagonal over here, which represents substrings of length two.
Now if we are analyzing a substring of length two, we would either fill two in the cell or one right.
Again why is that the case?
If you are having a substring that looks like this.
For example b b, we see that this itself is a palindrome.
And therefore we would say that the longest palindromic subsequence that can be formed from this substring
has a length of two.
Now, if you are dealing with a substring that looks like this, for example, which is b a, we see
that these two are not equal, but we can still form a palindromic subsequence of length one, which
is either b or a alone.
Okay, so that's why we would either have 1 or 2 filled in these cells over here.
Now let's see how it pans out.
So for this cell we see that we have p and q.
So these two are not equal.
So we are going to fill one over here.
And in this cell we have q and p.
They are not equal.
So we'll have one again.
Then we have p and we have r.
They are not equal.
So we have one over here as well.
Then we have r and we have p and they are not equal.
Therefore we have one over here as well.
And over here we have p and over here we have s.
So these two are also not equal.
And therefore we have one.
So all of these cells for the given string have the value one.
Now we proceed to the next diagonal which is this diagonal over here which represents strings of length
three.
Now when we are dealing with a string of length three, if these two characters are equal, then the
longest palindromic subsequence that we can form using this string would be two plus one.
Okay, because this is a palindrome because it's just one character.
Now, if these two characters are not equal, then we would have to consider this substring and this
substring separately and identify the larger value.
Okay.
So if length is equal to three either we will get the longest palindromic subsequence length as three.
If the first and last characters are equal, and if the first and last characters are not equal, then
we have to find the maximum between the length of the longest palindromic subsequence that we can form.
Considering this substring versus this substring over here okay, so let's go ahead and see how this
works out.
So over here for this cell we see that we have p and p.
They are equal.
Therefore we are going to apply this logic.
And that's just doing two plus one okay.
Again why is this the case.
Now let me just note down this over here.
So if we say that this cell is depee at I j.
Then, because the first and last characters for the string that we are considering are equal, I can
say that this is equal to two plus depee at I plus one j minus one.
Okay, so this is what we get when we remove or not consider the first and last characters.
And over here that's what we are seeing okay.
So in this case DP at I plus one J minus one is this cell over here which just represents Q.
And that's what we get right.
If you have p, q and p.
And if you are removing the first and last characters, you're just left with q.
So DP at I, j is equal to two plus dp at I plus one j minus one.
So that's how we get three over here.
And proceeding further over here we see we have Q and R and they are not equal.
So we have to identify the maximum between this case and this case.
Now notice that in the DP table this case over here is represented by this cell.
Okay where it starts at Q and goes up to P instead of R.
Right.
So that's q p.
And this case over here is represented by this cell over here where it starts at P and goes up to R
which is this substring okay.
So we have q p r and this is q p and this is p r.
And notice that q p is this cell and p r is this cell.
And because these are of lower length than the length of q p r we have already computed them because
we are iterating length wise.
So this cell over here is going to take the maximum value between this value and this value.
Now for this example over here we have one.
And over here we have one.
And the maximum between 1 and 1 is just one.
And therefore we will fill one over here.
Let's proceed.
Now we come to this cell over here and we see that we have P over here.
And we have P over here.
And they are equal right.
So we are dealing with p r p.
That's the substring that we are dealing with.
And p is equal to p.
Therefore the value that we are going to fill over here is two plus this value over here which is equal
to three.
Okay.
And that's the same thing that we discussed over here as well.
Now we proceed to the next cell, which is this cell over here.
And we see that we have are over here and we have s over here.
So we are dealing with r p s and r is not equal to s.
And therefore this cell over here will take the maximum value between this cell and this cell.
Now over here and here we have one.
So the maximum between these two values is one itself.
And that's why we fill one over here.
So that's how we were able to fill these cells.
Now we proceed to the next diagonal and we come over here.
We see we have P over here and we have R over here.
They are not equal.
Therefore this cell will take the maximum value between what we have over here and what we have over
here.
Okay.
So that's this case over here.
Now the maximum between 3 and 1 is three.
So we will fill three over here.
And then when we come to this cell we have Q over here.
And P over here.
They are not equal.
So this cell will take the maximum between 1 and 3.
And the greater between these two values is three.
So we'll fill three over here and over here also we see that we have p and s.
They are not equal.
Therefore we take the maximum between 3 and 1 which is equal to three.
And hence we fill three.
Over here we proceed to the next diagonal.
So we have p and p okay.
So they are equal now because they are equal we'll just take two plus whatever we have over here.
And over here we have one.
So two plus one is equal to three.
And therefore we will fill three over here.
And again notice this works.
So again this cell over here represents the case where we are starting at index zero and going up to
index four.
So that's this substring which is p q p r p okay.
Now notice that the longest palindromic subsequence that you can form is p p p and p has a length of
three.
And that's what you're getting over here okay.
Now we proceed to this cell and we have Q over here and S over here.
So we are dealing with this substring q p r p s.
And we see that q is not equal to s.
Therefore this cell will take the greater value between this value and this value.
And we have three and three over here.
So whatever we are going to fill over here is the maximum between these two which is three itself.
All right.
Now we come to the last cell over here, and at this point we have P and S, and they are not equal.
Therefore, this cell will take the maximum between this value and this value.
And that would be three itself okay.
So we fill three over here.
And this gives us the answer right.
Again notice this cell represents the longest palindromic subsequence length that we can form where
the substring involved starts at index zero and goes up to index five, which is in fact the problem
that is given to us.
So that's why once we are able to fill this cell, we'll just need to return this.
And this will be the answer.
And again notice in this depee table this cell would be depee at zero at n minus one okay.
So this is the zeroth row.
And this would be the n minus one column with respect to indexing.
Right.
Because the indexing starts at zero and goes up to n minus one for n columns.
So again at the end we'll just need to return depee at zero n minus one.
And this will give us the answer.
So this is how we will solve the longest palindromic subsequence question using the tabulation approach.