1
00:00:00,620 --> 00:00:01,760
Welcome back.

2
00:00:01,760 --> 00:00:10,370
Let's say the DP table is already filled with either true or false in the cells that represented valid

3
00:00:10,370 --> 00:00:13,040
substrings of the string that is given to us.

4
00:00:13,070 --> 00:00:21,830
Now let's discuss iterating lengthwise through this DP table to identify how many palindromic substrings

5
00:00:21,830 --> 00:00:22,850
can be formed.

6
00:00:22,880 --> 00:00:27,020
Now first let's make a few interesting observations.

7
00:00:27,920 --> 00:00:35,000
The first thing to note over here is that these cells in the DP table are not meaningful because, for

8
00:00:35,000 --> 00:00:36,830
example, let's take this cell over here.

9
00:00:36,830 --> 00:00:43,250
For this cell, the starting index is two and the ending index is equal to one.

10
00:00:43,250 --> 00:00:45,080
And that's not meaningful right.

11
00:00:45,080 --> 00:00:49,550
Because starting index has to be less than or equal to the ending index.

12
00:00:49,550 --> 00:00:52,400
So these cells are not meaningful.

13
00:00:52,400 --> 00:01:01,400
And to identify how many palindromic substrings can be formed or to identify how many times true occurs

14
00:01:01,400 --> 00:01:06,980
in this DP table over here, we do not need to check these invalid cells.

15
00:01:06,980 --> 00:01:13,730
We just need to count the number of times true occurs in the valid cells which have been filled over

16
00:01:13,730 --> 00:01:14,180
here.

17
00:01:14,180 --> 00:01:23,150
And notice that to count this, we do not need to go through each and every cell in a row wise manner,

18
00:01:23,150 --> 00:01:28,400
but rather we could just go diagonally starting with this diagonal over here.

19
00:01:28,400 --> 00:01:36,410
So when we go diagonally, notice that these cells over here represent substrings of length equal to

20
00:01:36,410 --> 00:01:42,890
one, because the starting index and the ending index for these cells are one and the same.

21
00:01:42,890 --> 00:01:46,460
So the length of these substrings is equal to one.

22
00:01:46,460 --> 00:01:51,800
Similarly these substrings over here have a length equal to two because.

23
00:01:51,800 --> 00:01:52,400
Notice over here.

24
00:01:52,400 --> 00:01:57,770
For example, this substring over here starts at index one and goes up to index two.

25
00:01:57,770 --> 00:02:00,560
So there are two characters in this substring.

26
00:02:00,560 --> 00:02:07,010
In a similar manner, the next iteration would represent substrings of length equal to three.

27
00:02:07,010 --> 00:02:11,900
And the next iteration represents substrings of length equal to four.

28
00:02:11,900 --> 00:02:14,960
And then we have length equal to five over here.

29
00:02:14,960 --> 00:02:20,990
And finally this substring over here starts at index zero and goes up to index five.

30
00:02:20,990 --> 00:02:23,090
So the length is equal to six.

31
00:02:23,090 --> 00:02:31,160
So we have seen over here why iterating diagonally makes sense because these over here don't represent

32
00:02:31,160 --> 00:02:32,600
valid substrings.

33
00:02:32,600 --> 00:02:40,010
We will also use iterating diagonally when we discuss the tabulation approach for solving the palindromic

34
00:02:40,010 --> 00:02:41,120
substrings question.

35
00:02:41,120 --> 00:02:49,370
Now that we know that we want to go through over this DP table diagonally iterating in this manner,

36
00:02:49,370 --> 00:02:53,000
let's discuss how this can be achieved in code.

37
00:02:53,000 --> 00:02:59,420
And let's go ahead and write the pseudo code of the approach that can be taken to achieve this.

38
00:02:59,420 --> 00:03:04,070
Now notice that over here the length of the substring is equal to one.

39
00:03:04,070 --> 00:03:09,110
The length of the substring in these cases is equal to two, and it goes on in this manner.

40
00:03:09,110 --> 00:03:13,130
And finally the length of this substring is equal to six.

41
00:03:13,310 --> 00:03:20,390
So if this is the string that is given to us, the length goes from one up to six.

42
00:03:20,390 --> 00:03:20,810
Okay.

43
00:03:20,810 --> 00:03:23,210
So we can say that for L.

44
00:03:24,010 --> 00:03:29,920
Is equal to one up to n, because n in this case is the length of the string which is given to us,

45
00:03:29,920 --> 00:03:31,480
and that's equal to six.

46
00:03:31,480 --> 00:03:36,040
So for L is equal to one up to n.

47
00:03:36,040 --> 00:03:43,780
And then let's find the value of I which represents the row and j which represents the column.

48
00:03:43,780 --> 00:03:51,550
Notice over here for the first diagonal I ranged from values zero up to five.

49
00:03:52,480 --> 00:03:54,280
For the second diagonal.

50
00:03:54,280 --> 00:04:00,610
When length was equal to two, I ranged from the value zero up to four.

51
00:04:00,790 --> 00:04:09,460
So we can make the observation that I is ranging from zero up to n minus L, because in this case n

52
00:04:09,460 --> 00:04:12,910
is equal to six and n minus l is equal to five.

53
00:04:12,910 --> 00:04:16,630
And over here n again is equal to six and length is equal to two.

54
00:04:16,660 --> 00:04:19,030
So n minus l is equal to four.

55
00:04:19,030 --> 00:04:22,900
So I is ranging from zero up to n minus l.

56
00:04:22,930 --> 00:04:30,760
Now having got the value of I we can say that j is equal to I plus l minus one.

57
00:04:30,760 --> 00:04:32,140
Now why is that the case.

58
00:04:32,140 --> 00:04:34,690
Let's just walk through this to understand this.

59
00:04:34,720 --> 00:04:36,970
So initially L is equal to one.

60
00:04:36,970 --> 00:04:40,300
And I is ranging from zero up to five.

61
00:04:40,300 --> 00:04:44,590
So I have zero, one, 234 and five.

62
00:04:44,590 --> 00:04:46,420
These are the values of I.

63
00:04:46,450 --> 00:04:53,260
Now let me find the value of j for each respective value of I and l is equal to one.

64
00:04:53,260 --> 00:04:55,750
So one minus one gives me zero.

65
00:04:55,750 --> 00:04:58,300
So j is just going to equal to I.

66
00:04:58,330 --> 00:05:05,080
So the various values of j in these instances are zero, one, two, three, four and five.

67
00:05:05,080 --> 00:05:12,490
So zero zero gives me this cell one one gives me this cell two two gives me this cell three three gives

68
00:05:12,490 --> 00:05:14,860
me this cell four four gives me this cell.

69
00:05:14,860 --> 00:05:17,620
And finally five five gives me this cell.

70
00:05:17,860 --> 00:05:19,780
Let's take one more example.

71
00:05:20,200 --> 00:05:22,240
Let's say l is equal to two.

72
00:05:22,240 --> 00:05:26,410
And when L is equal to two I ranges from 0 to 4.

73
00:05:26,410 --> 00:05:29,740
So I have zero one, two three and four.

74
00:05:29,740 --> 00:05:34,540
And then j is going to equal I plus l minus one.

75
00:05:34,720 --> 00:05:38,890
Because l is equal to two two minus one is equal to one.

76
00:05:38,890 --> 00:05:41,560
So j is going to equal I plus one.

77
00:05:41,560 --> 00:05:44,740
So when I is equal to zero j will equal one.

78
00:05:44,740 --> 00:05:48,070
When I is equal to one, j will be equal to two.

79
00:05:48,100 --> 00:05:50,380
Similarly over here j is equal to three.

80
00:05:50,380 --> 00:05:52,420
And then we have j is equal to four over here.

81
00:05:52,420 --> 00:05:54,550
And j is equal to five over here.

82
00:05:54,580 --> 00:06:02,440
Now zero comma one gives me this cell one comma two gives me this cell two comma three gives me this

83
00:06:02,440 --> 00:06:04,030
cell three comma four.

84
00:06:04,030 --> 00:06:06,280
Again you have three over here four over here.

85
00:06:06,280 --> 00:06:07,690
So that gives me this cell.

86
00:06:07,690 --> 00:06:10,570
And four comma five gives me this cell.

87
00:06:10,570 --> 00:06:14,710
Notice over here we have successfully iterated in a diagonal manner.

88
00:06:14,710 --> 00:06:23,740
So we can use this approach for iterating over the DP table in a diagonal manner or in a lengthwise

89
00:06:23,740 --> 00:06:24,220
manner.

90
00:06:24,220 --> 00:06:30,640
So for the memoization approach, once we have written the recursive function, and once we have ensured

91
00:06:30,640 --> 00:06:36,280
that we are storing what we are computing, we will first go through all the possible substrings and

92
00:06:36,280 --> 00:06:43,060
fill either true or false in the respective cells that represent the substring at hand.

93
00:06:43,060 --> 00:06:50,590
And then we will use this approach to iterate over the DP table diagonally or in a lengthwise manner

94
00:06:50,590 --> 00:06:57,040
to count the number of times true occurs in the DP table over here, and that would be the answer to

95
00:06:57,040 --> 00:06:57,790
the question.