1
00:00:00,140 --> 00:00:01,100
Welcome back.

2
00:00:01,220 --> 00:00:06,500
Let's now get into the code and solve the longest palindromic subsequence question.

3
00:00:06,500 --> 00:00:08,480
So we are given the string over here.

4
00:00:08,480 --> 00:00:13,790
And let's say n is the length of the string okay.

5
00:00:13,790 --> 00:00:18,200
And let's create a DP array which will have n rows and n columns.

6
00:00:18,200 --> 00:00:24,950
So I can say let dp is equal to array dot from length n okay.

7
00:00:24,950 --> 00:00:28,070
And we also need n columns.

8
00:00:29,060 --> 00:00:36,830
Now what we will do is we will fill every cell in this dp array with the value zero okay.

9
00:00:36,830 --> 00:00:43,670
Now what we have to do is as we have discussed in the previous video, we have to iterate lengthwise

10
00:00:43,670 --> 00:00:46,190
through this DP array okay.

11
00:00:46,370 --> 00:00:48,080
And again we know how to do that.

12
00:00:48,080 --> 00:00:55,460
And once we do that ultimately we will get the answer at DP at zero n minus one.

13
00:00:55,460 --> 00:00:59,000
And we have discussed this in the previous video and we would be returning that.

14
00:00:59,000 --> 00:01:04,370
So this is the approach that we are going to take and to iterate lengthwise through the cells in the

15
00:01:04,370 --> 00:01:05,000
DP array.

16
00:01:05,000 --> 00:01:06,710
We already know how to do that.

17
00:01:06,710 --> 00:01:07,970
We have written it many times.

18
00:01:07,970 --> 00:01:10,400
So we are going to have this nested for loop.

19
00:01:10,400 --> 00:01:16,670
So for let L is equal to one l less than equal to n l plus plus okay.

20
00:01:16,670 --> 00:01:25,460
Because l or length takes the values from one up to n, and for each value of l, we will have I, which

21
00:01:25,460 --> 00:01:28,730
will take the values from zero up to n minus l.

22
00:01:28,730 --> 00:01:34,220
So I can say I less than equal to n minus l I plus plus okay.

23
00:01:34,220 --> 00:01:40,400
And for each combination of I and l, j would be equal to I plus l minus one.

24
00:01:40,730 --> 00:01:41,450
All right.

25
00:01:41,480 --> 00:01:46,220
Now every ij combination gives us a cell in the DP table.

26
00:01:46,220 --> 00:01:52,820
And using this nested for loop structure we are iterating lengthwise or diagonally through the DP table.

27
00:01:52,820 --> 00:01:59,360
And over here first we are going to check whether I is equal to j because if these two are equal, we

28
00:01:59,360 --> 00:02:02,180
are just dealing with the substring of one character.

29
00:02:02,180 --> 00:02:04,850
And such a substring is a palindrome.

30
00:02:04,850 --> 00:02:10,850
And we can just say that the length of this particular substring, or the length of the longest palindromic

31
00:02:10,850 --> 00:02:15,980
subsequence of this particular substring, which just has one character, is equal to one.

32
00:02:15,980 --> 00:02:19,370
So here we'll set dp at ij is equal to one.

33
00:02:19,670 --> 00:02:29,900
Now if this is not the case, we will check whether s at I is equal to s at j okay.

34
00:02:29,900 --> 00:02:36,440
And if these two are equal then as we have discussed in the previous video, we can set dp at ij to

35
00:02:36,440 --> 00:02:42,410
be equal to two plus dp at I plus one j minus one.

36
00:02:43,160 --> 00:02:43,820
Okay.

37
00:02:44,390 --> 00:02:54,110
Else if these two characters are not equal, we would need to take a look at DP at I plus one j and

38
00:02:54,110 --> 00:02:56,900
dp at I j minus one.

39
00:02:56,900 --> 00:03:04,160
So we are only moving one pointer okay or one index and again in the DP table this would be the left

40
00:03:04,160 --> 00:03:07,280
and the bottom element of the cell that we are considering.

41
00:03:07,280 --> 00:03:09,860
So we have to take a look at these two cells.

42
00:03:09,860 --> 00:03:16,010
And because we were iterating lengthwise the length from I to J as you can see, would be greater than

43
00:03:16,010 --> 00:03:19,160
the length from I plus one to j or I to j minus one.

44
00:03:19,160 --> 00:03:25,460
So these two will be values that we have already calculated, and we just need to find the maximum between

45
00:03:25,460 --> 00:03:25,940
these two.

46
00:03:25,970 --> 00:03:29,540
So I can say math dot max between these two okay.

47
00:03:29,540 --> 00:03:32,330
So that's what we will assign to dp at ij.

48
00:03:33,950 --> 00:03:39,350
So dp at ij is equal to math dot max between this and this okay.

49
00:03:39,350 --> 00:03:40,160
And that's it.

50
00:03:40,160 --> 00:03:42,230
So this should solve this question.

51
00:03:42,230 --> 00:03:44,150
And finally we have to return the answer.

52
00:03:44,150 --> 00:03:47,060
And we have already returned the return statement over here.

53
00:03:47,060 --> 00:03:48,920
Return DP at zero n minus one.

54
00:03:48,920 --> 00:03:53,030
Now let's go ahead and run this code and see if it's passing all the test cases.

55
00:03:53,990 --> 00:03:55,580
And you can see that it's working.

56
00:03:55,580 --> 00:03:57,500
It's passing all the test cases.