1
00:00:00,530 --> 00:00:02,270
Hey there and welcome back.

2
00:00:02,270 --> 00:00:08,270
So we are done with the memoization approach for solving the palindromic substrings question.

3
00:00:08,270 --> 00:00:15,830
And we have got a solution with an O of n square time complexity and an O of n square space complexity.

4
00:00:16,190 --> 00:00:20,270
Let's now take a look at the tabulation approach for solving this question.

5
00:00:20,270 --> 00:00:25,040
To discuss this approach, let's say this is the string that is given to us.

6
00:00:25,040 --> 00:00:27,410
That's p q p r p s.

7
00:00:27,410 --> 00:00:30,080
And we will need a DP table over here.

8
00:00:30,080 --> 00:00:36,140
And again we have columns for each of the indices in the string that is given to us.

9
00:00:36,140 --> 00:00:41,180
And we have rows also for each of the indices in the string that is given to us.

10
00:00:41,180 --> 00:00:48,200
Now to come up with the tabulation approach is going to be very easy because we know already how to

11
00:00:48,200 --> 00:00:49,550
iterate diagonally.

12
00:00:50,180 --> 00:00:57,440
So what we need to do is we need to go through each cell in this DP table over here, which represents

13
00:00:57,440 --> 00:00:58,760
a valid substring.

14
00:00:58,760 --> 00:01:02,270
And we need to check whether it is a palindrome or not.

15
00:01:02,270 --> 00:01:06,620
And if it is a palindrome, we need to fill true in that particular cell.

16
00:01:06,620 --> 00:01:10,370
And if not we need to fill false in that particular cell.

17
00:01:10,370 --> 00:01:13,790
So let's just trace how the algorithm would do that.

18
00:01:13,790 --> 00:01:18,080
So initially we will iterate through these cells over here.

19
00:01:18,080 --> 00:01:24,080
And as we have discussed these cells represent substrings of length equal to one.

20
00:01:24,080 --> 00:01:29,510
Now if a substring has just one character we know that it is a palindrome.

21
00:01:29,510 --> 00:01:33,410
And therefore in all of these cells over here we will fill true.

22
00:01:33,410 --> 00:01:35,120
So let's go ahead and do that.

23
00:01:35,120 --> 00:01:37,760
So we have true in all of these cells.

24
00:01:37,760 --> 00:01:41,870
Now we proceed to the scenario where length is equal to two.

25
00:01:41,870 --> 00:01:50,540
And if a substring has just two characters we just need to check whether the character at index I and

26
00:01:50,540 --> 00:01:53,660
the character at index j are equal or not.

27
00:01:53,660 --> 00:01:59,990
So if they are equal, then we know that we have a palindrome and we can fill true in that particular

28
00:01:59,990 --> 00:02:00,530
cell.

29
00:02:00,530 --> 00:02:04,520
And otherwise we will fill false in the particular cell at hand.

30
00:02:04,520 --> 00:02:07,670
So let's go ahead and do that for this example.

31
00:02:07,670 --> 00:02:10,100
So over here we have p and q.

32
00:02:10,130 --> 00:02:11,330
They are not equal.

33
00:02:11,330 --> 00:02:13,220
So we can fill false over here.

34
00:02:14,150 --> 00:02:18,920
And over here we have Q and P and these are not equal.

35
00:02:18,920 --> 00:02:21,200
So we can again fill false.

36
00:02:21,200 --> 00:02:23,570
Over here we have p and r.

37
00:02:23,570 --> 00:02:24,740
These are not equal.

38
00:02:24,740 --> 00:02:26,390
So we can fill false over here.

39
00:02:26,390 --> 00:02:28,070
And then we have r over here.

40
00:02:28,070 --> 00:02:29,390
And we have P over here.

41
00:02:29,390 --> 00:02:30,800
These are not equal.

42
00:02:30,800 --> 00:02:32,480
So we can fill false over here.

43
00:02:32,480 --> 00:02:33,890
And then we have P over here.

44
00:02:33,890 --> 00:02:35,510
And we have s over here.

45
00:02:35,510 --> 00:02:36,800
These are not equal.

46
00:02:36,800 --> 00:02:39,020
So we fill false over here as well.

47
00:02:39,530 --> 00:02:44,780
Now we proceed to the next iteration which is through these cells over here.

48
00:02:44,780 --> 00:02:49,340
And for these cases we have substrings of length equal to three.

49
00:02:49,880 --> 00:02:57,650
Now if we have a substring of length equal to three we need to first check whether character at index

50
00:02:57,650 --> 00:03:00,740
I is equal to the character at index j.

51
00:03:00,740 --> 00:03:03,620
So this is the starting index and this is the ending index.

52
00:03:03,620 --> 00:03:11,960
And if these are equal then we also need to check the substring that starts at index I plus one and

53
00:03:11,960 --> 00:03:19,220
ends at j minus one to know whether this substring over here that starts at index I and goes till index

54
00:03:19,220 --> 00:03:21,860
j is a palindrome or not.

55
00:03:21,860 --> 00:03:29,360
Now the good thing is that because the length of this substring over here is less than the length of

56
00:03:29,360 --> 00:03:36,380
the substring that goes from I to j, we already have computed this because we were iterating length

57
00:03:36,380 --> 00:03:36,770
wise.

58
00:03:36,770 --> 00:03:43,760
So over here we already have the answers to all the substrings of length one, and we already have the

59
00:03:43,760 --> 00:03:51,200
answers to all the substrings of length two, which means that all the substrings of lower length are

60
00:03:51,200 --> 00:03:57,950
already computed, and we already have filled either true or false for those scenarios in the DP table

61
00:03:57,950 --> 00:03:58,370
over here.

62
00:03:58,370 --> 00:04:01,460
So let's proceed and trace the algorithm.

63
00:04:01,460 --> 00:04:05,810
So over here we have p and we have p itself at index two.

64
00:04:05,840 --> 00:04:07,460
So these two are equal.

65
00:04:07,460 --> 00:04:14,180
And therefore we just need to go ahead and check the substring which starts at index I plus one and

66
00:04:14,180 --> 00:04:16,220
goes till index j minus one.

67
00:04:16,220 --> 00:04:21,440
So I plus one is equal to one and j minus one is two minus one which is one.

68
00:04:21,440 --> 00:04:25,340
Now we know that a substring of length one is a palindrome.

69
00:04:25,340 --> 00:04:28,490
But then let's take a look at how the algorithm solves this.

70
00:04:28,490 --> 00:04:35,120
So the algorithm goes and checks dp at I plus one j minus one which is this over here.

71
00:04:35,730 --> 00:04:41,310
And over here we have already filled through and we can just take this value and fill it over here.

72
00:04:41,310 --> 00:04:43,200
So we get true over here as well.

73
00:04:43,650 --> 00:04:45,630
Now we proceed to the next cell.

74
00:04:45,630 --> 00:04:48,150
So we have Q over here and R.

75
00:04:48,180 --> 00:04:49,980
Now these are not equal.

76
00:04:49,980 --> 00:04:52,200
Therefore we can fill false over here.

77
00:04:52,200 --> 00:04:54,990
And then over here we have p and we have p.

78
00:04:54,990 --> 00:04:56,130
These are equal.

79
00:04:56,130 --> 00:05:01,500
Therefore we just take this value and fill it over here which is d p I plus one j minus one.

80
00:05:01,500 --> 00:05:02,850
So we have true over here.

81
00:05:02,850 --> 00:05:05,790
And then over here we have r and we have s.

82
00:05:05,790 --> 00:05:07,290
These two are not equal.

83
00:05:07,290 --> 00:05:09,300
So we can fill false over here.

84
00:05:09,780 --> 00:05:11,880
So we are done with this iteration.

85
00:05:11,880 --> 00:05:16,410
Now let's proceed to the case where length is equal to four.

86
00:05:16,410 --> 00:05:21,930
Again we check the characters at index zero and three for this cell.

87
00:05:21,930 --> 00:05:23,220
And they are not equal.

88
00:05:23,220 --> 00:05:24,960
So we can fill false over here.

89
00:05:25,670 --> 00:05:29,990
And for the next cell over here we have Q and we have P.

90
00:05:30,020 --> 00:05:31,310
These are not equal.

91
00:05:31,310 --> 00:05:33,500
So we can fill false over here as well.

92
00:05:33,620 --> 00:05:36,080
Over here we have p and we have s.

93
00:05:36,110 --> 00:05:37,370
These are not equal.

94
00:05:37,370 --> 00:05:39,440
So we can fill false over here as well.

95
00:05:39,440 --> 00:05:41,450
So we are done with this iteration.

96
00:05:41,450 --> 00:05:43,730
We proceed to the next iteration.

97
00:05:43,730 --> 00:05:47,600
So over here notice we have p and we have p.

98
00:05:47,600 --> 00:05:49,970
So these two are equal.

99
00:05:49,970 --> 00:05:57,050
Therefore we need to check d p I plus one j minus one which is this value over here which is already

100
00:05:57,050 --> 00:06:04,040
computed because the length of the substring that starts at I plus one and ends at j minus one, is

101
00:06:04,040 --> 00:06:08,870
lesser than the length of the substring that starts at I and goes till j.

102
00:06:08,870 --> 00:06:14,570
And because we've been iterating length wise, we have already calculated this, and we have stored

103
00:06:14,570 --> 00:06:15,380
false over here.

104
00:06:15,380 --> 00:06:19,070
And because these two are equal we need to check this substring.

105
00:06:19,070 --> 00:06:20,240
And this is false.

106
00:06:20,240 --> 00:06:22,580
So we can just take it and fill it over here.

107
00:06:22,580 --> 00:06:23,840
So we have false over here.

108
00:06:23,840 --> 00:06:26,000
And then over here we have Q and S.

109
00:06:26,000 --> 00:06:27,320
They are not equal.

110
00:06:27,320 --> 00:06:29,810
Therefore we can fill false over here as well.

111
00:06:29,810 --> 00:06:32,510
And then finally we come to this string.

112
00:06:32,510 --> 00:06:36,080
So over here we have P and over here we have s.

113
00:06:36,110 --> 00:06:37,310
They are not equal.

114
00:06:37,310 --> 00:06:39,620
So we can fill false over here as well.

115
00:06:39,620 --> 00:06:47,270
And in this manner we have completed iterating length wise and filling the cells in this DP table over

116
00:06:47,270 --> 00:06:50,450
here which represented valid substrings.

117
00:06:50,690 --> 00:06:57,890
Now to identify the number of palindromic substrings we just need a count variable.

118
00:06:57,890 --> 00:07:03,500
And whenever we are filling true in this table over here we would increment that count variable.

119
00:07:03,500 --> 00:07:07,490
So in that way we can identify the number of palindromic substrings.

120
00:07:07,490 --> 00:07:10,460
And finally we can return this count variable.

121
00:07:10,460 --> 00:07:15,710
So this is the tabulation approach for solving the palindromic substrings question.