1
00:00:00,080 --> 00:00:00,920
Welcome back.

2
00:00:00,920 --> 00:00:07,310
Let's now get into the code and implement the tabulation approach for solving the palindromic substrings

3
00:00:07,310 --> 00:00:07,850
question.

4
00:00:07,850 --> 00:00:10,490
So we have this function over here count substrings.

5
00:00:10,490 --> 00:00:13,460
And to this function we are given this string over here.

6
00:00:13,460 --> 00:00:17,420
Now let's say n is the length of the given string.

7
00:00:17,420 --> 00:00:20,510
So let n is equal to s dot length okay.

8
00:00:20,510 --> 00:00:25,280
And finally again we have to count the number of palindromic substrings.

9
00:00:25,280 --> 00:00:27,230
And for that we would need a variable.

10
00:00:27,230 --> 00:00:28,760
And let me just call it rest.

11
00:00:28,760 --> 00:00:31,220
And let's initialize this to be equal to zero.

12
00:00:31,220 --> 00:00:35,270
And we'll keep counting the number of substrings which are palindromes.

13
00:00:35,270 --> 00:00:37,820
And finally we will just return s.

14
00:00:38,150 --> 00:00:38,660
Okay.

15
00:00:38,660 --> 00:00:47,000
Now to continue let's create a DP table which is going to be a 2D array having n rows and n columns.

16
00:00:47,000 --> 00:00:53,300
So let's say net dp is equal to array dot from and we can write array n over here.

17
00:00:56,020 --> 00:00:56,950
R a n.

18
00:00:56,950 --> 00:01:03,940
Okay, now what we will do is we will fill every cell in this depee table with the value false.

19
00:01:04,750 --> 00:01:12,850
Okay, let's proceed and iterate over the cells in this DP table in a lengthwise manner or in a diagonal

20
00:01:12,850 --> 00:01:13,420
manner.

21
00:01:13,420 --> 00:01:17,500
And for this we can just use the nested for loop method that we have discussed.

22
00:01:17,500 --> 00:01:26,020
So I can say for let L is equal to one l less than equal to n l plus plus because L stands for length

23
00:01:26,020 --> 00:01:32,050
and the length goes from one up to n, and for each value of l, I will have another variable I.

24
00:01:32,080 --> 00:01:41,830
So for let I is equal to zero, I less than or equal to n minus l I plus plus okay.

25
00:01:41,830 --> 00:01:48,670
And for each combination of I and l we will have another variable j which is going to equal I plus l

26
00:01:48,670 --> 00:01:49,660
minus one.

27
00:01:50,110 --> 00:01:52,840
And we have discussed this in detail in the previous video.

28
00:01:52,840 --> 00:01:59,410
Now whenever we get a combination of I and J over here, we are actually going through a cell on a particular

29
00:01:59,410 --> 00:02:03,610
diagonal, or we are iterating through the DP table in a diagonal manner.

30
00:02:03,610 --> 00:02:10,240
Now what we are going to do is first we are going to check if I is equal to J, because if these two

31
00:02:10,240 --> 00:02:14,530
are equal, then we are just dealing with the substring which has one character.

32
00:02:14,530 --> 00:02:19,030
And we know that a single character substring is always a palindrome.

33
00:02:19,030 --> 00:02:25,180
So in this case I can say dp at I j is equal to true okay.

34
00:02:25,180 --> 00:02:31,570
And whenever we will set dp at ij to be true, we will also increment rest because that's what we will

35
00:02:31,570 --> 00:02:33,190
finally return over here okay.

36
00:02:33,190 --> 00:02:35,350
So we will return rest finally over here.

37
00:02:36,380 --> 00:02:37,640
Okay, I've already written that.

38
00:02:37,640 --> 00:02:41,900
So let's remove that and probably let's reduce the space over here.

39
00:02:43,500 --> 00:02:43,890
All right.

40
00:02:43,890 --> 00:02:46,560
So over here we have set depee at IJ to be true.

41
00:02:46,560 --> 00:02:48,420
And therefore let's increment this.

42
00:02:51,390 --> 00:02:53,430
All right, and let's proceed.

43
00:02:53,430 --> 00:03:01,500
Now, if these two are not equal, then we will go ahead and check if s at I is equal to s at j.

44
00:03:01,590 --> 00:03:01,890
Okay.

45
00:03:01,890 --> 00:03:06,210
So else if s at I is equal to s at j.

46
00:03:06,570 --> 00:03:13,860
Now if these two characters are equal, then for the substring that we are considering to be a palindrome,

47
00:03:13,860 --> 00:03:20,160
we would either have to be considering a substring of length two okay, which can be checked by checking

48
00:03:20,160 --> 00:03:29,940
whether j is equal to I plus one, or if that is not the case, then depee at I plus one j minus one

49
00:03:29,940 --> 00:03:32,280
also has to be a palindrome.

50
00:03:32,280 --> 00:03:34,230
And again what is it that we are doing over here?

51
00:03:34,230 --> 00:03:37,620
Let me quickly write it and explain it one more time.

52
00:03:37,620 --> 00:03:44,820
So let's say we have I over here and then we have a few more characters okay.

53
00:03:44,820 --> 00:03:46,560
And let's say we have J over here.

54
00:03:46,560 --> 00:03:50,880
Now in this case we are seeing that's at I and S at J are equal.

55
00:03:50,880 --> 00:03:55,260
So whatever character is over here is equal to the character that we have over here.

56
00:03:55,260 --> 00:04:02,130
Now if these two characters are equal for this complete substring to be a palindrome, whatever is in

57
00:04:02,130 --> 00:04:05,970
between these characters also has to be a palindrome.

58
00:04:05,970 --> 00:04:06,360
Right.

59
00:04:06,360 --> 00:04:09,660
And this index over here would be I plus one.

60
00:04:09,660 --> 00:04:12,030
And this index over here would be j minus one.

61
00:04:12,030 --> 00:04:12,450
Okay.

62
00:04:12,450 --> 00:04:18,600
And because we are iterating lengthwise and notice that the length of this substring over here which

63
00:04:18,600 --> 00:04:25,140
starts at index I plus one and goes up to j minus one, is lower than the length of this complete substring,

64
00:04:25,140 --> 00:04:28,020
which starts at index I and goes up to index j.

65
00:04:28,050 --> 00:04:34,470
Therefore, and because we are iterating lengthwise, we would already have calculated this before we

66
00:04:34,470 --> 00:04:36,330
come and try to calculate this.

67
00:04:36,330 --> 00:04:43,410
So that is why we can just directly refer to dp at I plus one j minus one to check whether this substring

68
00:04:43,410 --> 00:04:49,380
over here, which is the substring that starts at index I plus one and goes up to index j minus one

69
00:04:49,380 --> 00:04:51,030
is a palindrome or not.

70
00:04:51,030 --> 00:04:51,420
Okay.

71
00:04:51,420 --> 00:04:56,610
So if these two characters are equal, either we should be dealing with a substring that just has two

72
00:04:56,610 --> 00:05:02,940
characters, or the substring which is in between I and j should be a palindrome.

73
00:05:02,940 --> 00:05:09,840
So if either of these is true, and if this is true, then we can set dp at I j to be equal to two.

74
00:05:12,930 --> 00:05:13,560
Okay.

75
00:05:13,560 --> 00:05:17,670
And whenever we set depee at IJ to be true, we have to increment rest.

76
00:05:17,700 --> 00:05:20,430
So rest plus is equal to one.

77
00:05:20,430 --> 00:05:25,440
And if these two are not equal then we will just say dp ij.

78
00:05:28,560 --> 00:05:29,610
Is equal to false.

79
00:05:29,610 --> 00:05:35,250
And again we can avoid this also because we have already said every cell in the DB table to be false.

80
00:05:35,250 --> 00:05:36,750
But okay, you can write it as well.

81
00:05:36,750 --> 00:05:37,500
It does not matter.

82
00:05:37,500 --> 00:05:37,920
Okay.

83
00:05:37,920 --> 00:05:40,890
Again it means that it's not a palindrome and that's it.

84
00:05:40,890 --> 00:05:46,470
So what we have done over here is we have created this DB table, and we have iterated through the cells

85
00:05:46,470 --> 00:05:48,810
in the DB table in a length wise manner.

86
00:05:48,810 --> 00:05:54,570
And wherever we found a substring that is a palindrome, we have said depth ij to be equal to true.

87
00:05:54,570 --> 00:06:01,800
And whenever we did that, we incremented this and therefore rest now has the count of palindromic substrings

88
00:06:01,800 --> 00:06:03,420
and we are returning it over here.

89
00:06:03,420 --> 00:06:06,210
So this is the tabulation approach for solving this question.

90
00:06:06,210 --> 00:06:10,230
Now let's go ahead and run this code and see if it's passing all the test cases.

91
00:06:11,890 --> 00:06:13,840
And you can see that it's working.

92
00:06:13,840 --> 00:06:15,670
It's passing all the test cases.

93
00:06:15,670 --> 00:06:20,320
So this is the tabulation approach for solving the palindromic substrings question.