1
00:00:00,110 --> 00:00:04,430
Let's now get into the code for solving the palindromic substrings question.

2
00:00:04,460 --> 00:00:08,630
So over here we are going to implement the memoization approach.

3
00:00:08,630 --> 00:00:11,270
And notice we are given this function.

4
00:00:11,270 --> 00:00:14,510
And to this function the string S is given.

5
00:00:14,540 --> 00:00:18,860
Now let's say n is the length of the given string.

6
00:00:19,700 --> 00:00:21,680
And let's create a DP table.

7
00:00:21,680 --> 00:00:27,740
So we would need a 2d dp table which will have n rows and n columns.

8
00:00:27,770 --> 00:00:28,220
Okay.

9
00:00:28,220 --> 00:00:30,530
So let's go ahead and implement that.

10
00:00:33,650 --> 00:00:34,430
Okay.

11
00:00:34,430 --> 00:00:37,160
And we would also need n columns.

12
00:00:38,210 --> 00:00:44,480
And what we will do is we will fill every cell in this DP table with the value minus one.

13
00:00:45,980 --> 00:00:46,550
Okay.

14
00:00:46,550 --> 00:00:49,370
And this is going to be a recursive solution.

15
00:00:49,370 --> 00:00:51,410
And we are going to use a helper function.

16
00:00:51,410 --> 00:00:53,330
Let me just call it helper itself.

17
00:00:53,330 --> 00:01:00,440
To this function we will be passing two indices which represent the start index and the end index okay.

18
00:01:00,440 --> 00:01:03,950
And a combination of I and j will give us a substring.

19
00:01:03,950 --> 00:01:07,040
In this manner we will go through all the relevant substrings.

20
00:01:07,040 --> 00:01:13,070
And using this helper function, wherever we find a substring which is a palindrome, we will fill the

21
00:01:13,070 --> 00:01:14,870
value true in the DP table.

22
00:01:14,900 --> 00:01:15,410
Okay.

23
00:01:15,410 --> 00:01:18,410
So let's write the details of this helper function later.

24
00:01:18,410 --> 00:01:21,350
And we would have to call this helper function for the first time.

25
00:01:21,350 --> 00:01:26,720
And when we do that we will pass the indices zero and n minus one to it okay.

26
00:01:26,720 --> 00:01:30,860
Because that's the first index and the last index of the given string.

27
00:01:30,860 --> 00:01:36,890
Once we are done with this, we would just have to iterate through the DP table in a diagonal or length

28
00:01:36,890 --> 00:01:41,930
wise manner, as we have discussed in the previous video, and we would just have to count the number

29
00:01:41,930 --> 00:01:43,490
of times true occurs.

30
00:01:43,520 --> 00:01:47,960
Okay, let's have a variable race where we are going to store this particular count.

31
00:01:47,960 --> 00:01:50,450
And finally we will be just returning this.

32
00:01:51,140 --> 00:01:51,590
Okay.

33
00:01:51,590 --> 00:01:57,080
Now let's go ahead and write the code for iterating through the DP table in a diagonal manner.

34
00:01:57,080 --> 00:01:58,280
It's pretty straightforward.

35
00:01:58,280 --> 00:02:00,410
So we'll have two for loops.

36
00:02:00,410 --> 00:02:07,880
And over here I will say for let L is equal to one L less than or equal to n l plus plus.

37
00:02:07,880 --> 00:02:15,260
Because l or length can take the values from one up to n, and for each value of L will have another

38
00:02:15,260 --> 00:02:15,740
variable.

39
00:02:15,740 --> 00:02:23,570
Let us call it I, and I will take the values from zero up to n minus n, so I less than equal to n

40
00:02:23,570 --> 00:02:25,670
minus l okay.

41
00:02:25,670 --> 00:02:27,110
And I plus plus.

42
00:02:27,110 --> 00:02:27,830
All right.

43
00:02:27,830 --> 00:02:31,550
So we are getting a combination of L and I.

44
00:02:31,550 --> 00:02:37,880
And for each of these combinations we will take J as I plus L minus one.

45
00:02:38,300 --> 00:02:42,410
And we have discussed the logic for this in detail in the previous video okay.

46
00:02:42,410 --> 00:02:49,310
And each combination of I and J will give us one of the cells when we are iterating through the DP table

47
00:02:49,310 --> 00:02:58,490
in a length wise manner or diagonally, and we will just check if dp at I, j is equal to true, and

48
00:02:58,490 --> 00:03:01,910
if it is equal to true, then we will increment rest.

49
00:03:02,000 --> 00:03:02,960
And that's it.

50
00:03:02,960 --> 00:03:06,230
Now all that remains is to complete the helper function.

51
00:03:06,230 --> 00:03:10,130
So let's go ahead and do that okay.

52
00:03:10,130 --> 00:03:16,100
So in the helper function over here we are going to write the base case as well as the recursive case.

53
00:03:19,400 --> 00:03:20,210
Okay.

54
00:03:20,300 --> 00:03:22,490
Now, what would be the base case?

55
00:03:22,490 --> 00:03:27,140
The base case is the scenario where I and J are equal okay.

56
00:03:27,140 --> 00:03:33,740
So if I is equal to j then we can just say that dp at I j is equal to true okay.

57
00:03:33,740 --> 00:03:36,950
Because we are just dealing with a substring of length one.

58
00:03:36,950 --> 00:03:40,850
And we know that a string of length one is in fact a palindrome.

59
00:03:40,850 --> 00:03:45,080
And if we get true over here, we will just return dp at ij.

60
00:03:45,110 --> 00:03:45,740
Okay.

61
00:03:45,740 --> 00:03:51,770
Now after the base case, before we go ahead and do the recursive case and do these computations over

62
00:03:51,770 --> 00:03:57,350
here, we are going to check whether we have already computed and stored this in depth ij.

63
00:03:57,350 --> 00:04:03,920
And for that we will check whether dp at ij is not equal to minus one, because if it's not equal to

64
00:04:03,920 --> 00:04:09,890
minus one, the reason for it not being minus one is that we have computed and stored it in dp at ij

65
00:04:09,890 --> 00:04:11,090
because node is over here.

66
00:04:11,090 --> 00:04:15,740
Initially we had filled every cell in the DP table with the value minus one.

67
00:04:15,740 --> 00:04:22,160
So if dp at ij is not equal to minus one, then we don't need to do any computations, but rather we

68
00:04:22,160 --> 00:04:25,460
will just return dp at ij okay.

69
00:04:25,460 --> 00:04:26,990
And then we proceed.

70
00:04:26,990 --> 00:04:30,890
So if this is not the case then we proceed and do computations.

71
00:04:30,890 --> 00:04:36,920
And then we will store the respective value that we get at dp at ij and then return dp at ij.

72
00:04:36,920 --> 00:04:38,690
So that's what we are going to do over here.

73
00:04:38,690 --> 00:04:41,570
So let's go ahead and continue with the code.

74
00:04:41,570 --> 00:04:47,960
So we are going to check whether s at I is equal to s at J.

75
00:04:48,110 --> 00:04:48,560
Okay.

76
00:04:48,560 --> 00:04:50,690
So again this is an if statement.

77
00:04:50,690 --> 00:05:00,050
So if these two characters are equal and if either this substring that we are considering just has two

78
00:05:00,050 --> 00:05:00,650
characters.

79
00:05:00,650 --> 00:05:05,270
And for checking that we can just check whether j is equal to I plus one, because if j is equal to

80
00:05:05,270 --> 00:05:08,930
I plus one, it means that the substring just has two characters.

81
00:05:08,930 --> 00:05:14,660
And over here, if this is true, it means that those two characters are equal and therefore we are

82
00:05:14,660 --> 00:05:15,710
dealing with a palindrome.

83
00:05:15,710 --> 00:05:21,290
Okay, so either this has to be true or if these two characters are equal.

84
00:05:21,290 --> 00:05:27,560
And then once you remove those two characters, whatever you are left with, that also should be a palindrome

85
00:05:27,560 --> 00:05:33,680
for the substring that starts at I and goes up to j to be a palindrome, and to check that we will just

86
00:05:33,680 --> 00:05:39,560
recursively call the same helper function which we are writing over here, and we will pass I plus one

87
00:05:39,560 --> 00:05:41,600
to it and j minus one to it.

88
00:05:41,600 --> 00:05:47,360
So basically we are just removing these two characters, and we are checking whether the remaining substring

89
00:05:47,360 --> 00:05:49,040
is a palindrome or not.

90
00:05:49,040 --> 00:05:49,520
Okay.

91
00:05:49,520 --> 00:05:58,490
So if this is true and if either of these is true then we will just say depee at I j is equal to true.

92
00:05:58,490 --> 00:05:58,910
Okay.

93
00:05:58,910 --> 00:06:01,010
And I think I've missed a bracket over here.

94
00:06:01,010 --> 00:06:02,240
So let's correct that.

95
00:06:02,240 --> 00:06:09,500
And if this is not the case then we will just say dp at I j is equal to false.

96
00:06:09,500 --> 00:06:10,190
Okay.

97
00:06:10,190 --> 00:06:12,560
Now there's one more thing that we have to do over here.

98
00:06:12,560 --> 00:06:18,710
We have to check the two cases where we are only moving one index at a time okay.

99
00:06:18,710 --> 00:06:20,720
So in this case let's just move I.

100
00:06:20,750 --> 00:06:23,660
So this would be helper I plus one J.

101
00:06:24,530 --> 00:06:28,760
And over here we will have the case where we are only moving J.

102
00:06:28,760 --> 00:06:29,000
Okay.

103
00:06:29,000 --> 00:06:30,770
It would be I and j minus one.

104
00:06:30,770 --> 00:06:35,900
So we have to check these two scenarios as well to see whether we are getting palindromes or not.

105
00:06:35,900 --> 00:06:36,680
All right.

106
00:06:36,680 --> 00:06:37,610
So that's it.

107
00:06:37,610 --> 00:06:39,140
Now this should take care of it.

108
00:06:39,140 --> 00:06:41,360
Now I see there is a error over here.

109
00:06:41,360 --> 00:06:42,830
So I think I've made a mistake.

110
00:06:42,830 --> 00:06:44,690
Let me quickly check that okay.

111
00:06:44,690 --> 00:06:46,640
So I see there's a missing bracket over here.

112
00:06:47,590 --> 00:06:48,670
And that's it.

113
00:06:48,670 --> 00:06:52,870
Now let's go ahead and run this code and see if it's passing all the test cases.

114
00:06:54,900 --> 00:06:56,070
And it's working.

115
00:06:56,070 --> 00:07:01,320
So this is the memoization approach for solving the palindromic substrings question.