1
00:00:00,930 --> 00:00:07,620
The palindromic substrings problem is a question that can be solved using dynamic programming.

2
00:00:07,620 --> 00:00:09,690
But how to identify that?

3
00:00:09,690 --> 00:00:12,060
Let's discuss that in this video.

4
00:00:12,090 --> 00:00:19,860
Now, an important thing that you need to keep in mind is that depee is useful in counting problems.

5
00:00:19,890 --> 00:00:26,340
Notice that in the palindromic substrings question, we are asked to count the number of substrings

6
00:00:26,340 --> 00:00:30,030
that we can form that are palindromes from the given string.

7
00:00:30,030 --> 00:00:34,710
So this is one hint that you can use to identify that this is a DP problem.

8
00:00:34,710 --> 00:00:41,910
Another important thing to notice in the palindromic substrings question is that there are overlapping

9
00:00:41,910 --> 00:00:42,930
subproblems.

10
00:00:42,930 --> 00:00:49,110
To understand this, let's take the example where the string given to us is a, a, b, c.

11
00:00:49,290 --> 00:00:57,450
We have already discussed in the previous video that we would have to check a, a, b and a b c in two

12
00:00:57,450 --> 00:01:02,850
separate recursive calls to identify whether these are palindromes or not.

13
00:01:02,850 --> 00:01:10,290
Again, within these two recursive calls, we will have instances where we only increment one pointer.

14
00:01:10,290 --> 00:01:14,820
So over here, if we only increment this pointer, we would get a b.

15
00:01:14,820 --> 00:01:20,160
And similarly over here, if we only increment this pointer, we would again get a b.

16
00:01:20,190 --> 00:01:26,280
Notice that the same subproblem is occurring in two branches of the recursion tree.

17
00:01:26,640 --> 00:01:34,410
The palindromic substrings question also has optimal substructure, because solving these subproblems

18
00:01:34,410 --> 00:01:40,950
will help us to solve the original problem, because ultimately we are trying to count the number of

19
00:01:40,950 --> 00:01:43,080
substrings that are palindromes.

20
00:01:43,080 --> 00:01:50,190
So in this video, we have discussed the things that help us identify this question as a DP question.