1
00:00:00,700 --> 00:00:01,750
Welcome back.

2
00:00:01,750 --> 00:00:08,020
So this is the approach that we have discussed already in detail when we were discussing the palindromic

3
00:00:08,020 --> 00:00:09,100
substrings question.

4
00:00:09,100 --> 00:00:10,900
So this is the tabulation approach.

5
00:00:10,900 --> 00:00:15,700
So again remember we had this table over here and we iterated lengthwise.

6
00:00:15,700 --> 00:00:18,970
And we either filled true or false in these cells.

7
00:00:18,970 --> 00:00:20,650
So that's how we solved that question.

8
00:00:20,650 --> 00:00:26,590
Now let's make use of this and try to solve the longest palindromic substring.

9
00:00:26,590 --> 00:00:29,710
So how we are going to solve this is we'll have a variable.

10
00:00:29,710 --> 00:00:31,510
Let's just call it longest.

11
00:00:32,200 --> 00:00:36,700
And initially, let's say longest is just an empty string.

12
00:00:36,760 --> 00:00:44,260
Now what we will do is as we go through these diagonals, or as we iterate through these cells in a

13
00:00:44,260 --> 00:00:51,820
length wise manner, whenever we get true, we will fill that particular substring to longest.

14
00:00:51,850 --> 00:00:52,330
Okay.

15
00:00:52,330 --> 00:00:54,160
So let's see how that pans out.

16
00:00:54,160 --> 00:01:00,760
So initially for example, when we are over here we get true and we will set longest to P okay.

17
00:01:00,760 --> 00:01:03,910
Because it's starting at zero and going up to index zero.

18
00:01:03,910 --> 00:01:05,650
And this will keep happening.

19
00:01:05,650 --> 00:01:10,960
And when we come over here longest would be s because again we have true over here.

20
00:01:10,960 --> 00:01:16,720
And we will change whatever we had previously in longest to the new value that we're getting over here,

21
00:01:16,720 --> 00:01:22,030
or to the new string for which we have identified that that particular substring is a palindrome.

22
00:01:22,030 --> 00:01:27,370
So at the end of this iteration, longest will be the substring s.

23
00:01:27,400 --> 00:01:27,970
Okay.

24
00:01:27,970 --> 00:01:33,190
Now when we go through these cells over here we see that everything is false.

25
00:01:33,190 --> 00:01:35,230
So longest does not change.

26
00:01:35,230 --> 00:01:42,310
And then when we come to this part over here to the third iteration, we get true over here.

27
00:01:42,310 --> 00:01:46,990
And at this point longest would be changed to p q p okay.

28
00:01:46,990 --> 00:01:52,810
And then we get again true over here, at which point longest would be changed to p r p.

29
00:01:52,840 --> 00:01:57,820
Notice that whenever we are getting true, we will be getting a substring which will either have the

30
00:01:57,820 --> 00:02:03,850
same length as the string which is already stored in longest or a greater length.

31
00:02:03,850 --> 00:02:08,200
And the reason for this is because we are iterating length wise.

32
00:02:08,200 --> 00:02:10,480
Okay, so the length over here is one.

33
00:02:10,480 --> 00:02:13,510
The length over here is two, the length over here is three.

34
00:02:13,510 --> 00:02:15,340
And it goes on in this manner okay.

35
00:02:15,340 --> 00:02:21,790
So again over here for this example because we have false in all of these cells, the answer finally

36
00:02:21,790 --> 00:02:22,930
will be p r p.

37
00:02:22,930 --> 00:02:26,080
And that is what we will finally just return.

38
00:02:26,080 --> 00:02:28,270
So this is how we can solve this question.

39
00:02:28,270 --> 00:02:30,520
Notice that it's pretty straightforward.

40
00:02:30,520 --> 00:02:37,750
It's just a minor tweak to the solution that we had come up with for the palindromic substring question.