1
00:00:01,860 --> 00:00:09,960
In this video, let's try to make a few interesting observations, and this will help us build the intuition

2
00:00:09,960 --> 00:00:15,360
necessary to come up with the approach for solving the palindromic substrings question.

3
00:00:15,420 --> 00:00:19,230
So for this, let's take a look at a few cases.

4
00:00:19,230 --> 00:00:26,250
Let's say the string that is given to us is either a b a or a b b a.

5
00:00:26,670 --> 00:00:35,850
We in either of these cases can see that the first character and the last character are equal, and

6
00:00:35,850 --> 00:00:41,130
if that is the case, then we would have to check the remaining string.

7
00:00:41,130 --> 00:00:43,230
So in this case that would be this part.

8
00:00:43,230 --> 00:00:45,660
And in this case that would be this part.

9
00:00:45,660 --> 00:00:53,760
To understand whether the whole string is a palindrome or not, let's say the pointer that is pointing

10
00:00:53,790 --> 00:00:59,850
to this character is I, and the pointer that's pointing to the last character is J.

11
00:00:59,850 --> 00:01:01,980
And that's the case over here as well.

12
00:01:01,980 --> 00:01:05,940
Now for identifying the remaining part of the string.

13
00:01:05,940 --> 00:01:14,700
Notice that the pointers I and J would be pointing to I plus one and j minus one, which would help

14
00:01:14,700 --> 00:01:18,450
us to identify the remaining part of the string.

15
00:01:18,540 --> 00:01:20,220
Now let's take another case.

16
00:01:20,220 --> 00:01:24,330
Let's say the string that is given to us is AA ba.

17
00:01:24,750 --> 00:01:29,520
Now over here again we see that a and A are equal.

18
00:01:29,520 --> 00:01:35,910
But when we check the remaining part of the string, we see that it's not a palindrome.

19
00:01:35,910 --> 00:01:41,400
And we can conclude that a, a, b a is not a palindrome.

20
00:01:41,400 --> 00:01:47,340
But because in this question we need to identify all palindromic substrings.

21
00:01:47,340 --> 00:01:55,590
Therefore, we can't just stop at this, but rather we would need to still check the substring a, b

22
00:01:55,590 --> 00:01:59,070
a, and we would in fact find a palindrome over here.

23
00:01:59,070 --> 00:02:08,760
So if I were pointing at this character and if J were pointing at this character to identify this substring,

24
00:02:08,760 --> 00:02:14,430
we would have to only increment I and keep j where it is itself.

25
00:02:14,430 --> 00:02:20,940
So this substring over here is represented by I plus one and j itself.

26
00:02:21,590 --> 00:02:23,000
In a similar manner.

27
00:02:23,000 --> 00:02:30,770
If the string given to us where a, b a a, even though these two are equal, and we see that the remaining

28
00:02:30,770 --> 00:02:34,070
string is not a palindrome, we can't stop there.

29
00:02:34,070 --> 00:02:40,520
We would also need to check this substring over here, which is given by I remaining where it was,

30
00:02:40,520 --> 00:02:44,330
but j changing from j to j minus one.

31
00:02:44,330 --> 00:02:52,790
So what we have learned over here is that to identify all the possible palindromic substrings we have

32
00:02:52,790 --> 00:02:54,140
to do three checks.

33
00:02:54,140 --> 00:02:59,720
So that's one check over here which is I plus one and J minus one.

34
00:02:59,720 --> 00:03:05,240
And the second case would be I plus one j and I j minus one.

35
00:03:05,240 --> 00:03:11,840
Now this over here will help us to identify whether the substring that we are considering, which is

36
00:03:11,840 --> 00:03:14,990
from I to J, is a palindrome or not.

37
00:03:14,990 --> 00:03:22,490
But these two calls over here will help us to identify other possible substrings by just moving one

38
00:03:22,490 --> 00:03:29,660
of the indices at a time when we implement the code for this, we would achieve these three checks by

39
00:03:29,660 --> 00:03:32,240
just using recursive calls for it.

40
00:03:32,240 --> 00:03:35,300
Now let's make a few more interesting observations.

41
00:03:35,300 --> 00:03:37,550
So for this let's make some space.

42
00:03:37,550 --> 00:03:43,880
Now think of the case that you are given a string which just has one character.

43
00:03:43,880 --> 00:03:49,640
Let's say it's just a now this character or this string is a palindrome.

44
00:03:49,640 --> 00:03:56,180
And notice that for identifying this, we just need to check whether the two pointers are pointing at

45
00:03:56,180 --> 00:03:57,140
the same character.

46
00:03:57,140 --> 00:04:03,980
So if I and J which are the two pointers that we will use, if these two are pointing at the same character,

47
00:04:03,980 --> 00:04:07,190
then this substring is definitely a palindrome.

48
00:04:07,490 --> 00:04:13,010
Another interesting observation that we can make is let's say the string that we are considering is

49
00:04:13,010 --> 00:04:13,580
AA.

50
00:04:13,580 --> 00:04:20,000
So it just has two characters and I is pointing at A and j is pointing also at a.

51
00:04:20,000 --> 00:04:21,590
So these two are equal.

52
00:04:21,590 --> 00:04:27,950
Now basis what we have discussed over here we would increment I and decrement j.

53
00:04:27,950 --> 00:04:36,230
But if we do that j would become less than I, which is not a valid case because I is the starting index

54
00:04:36,230 --> 00:04:37,880
and j is the ending index.

55
00:04:37,880 --> 00:04:41,540
And j always has to be greater than or equal to I.

56
00:04:41,570 --> 00:04:50,180
So to avoid this type of a scenario, if we see that the characters at index I and j are equal, not

57
00:04:50,180 --> 00:04:57,620
only do we need to check the case where we pass I plus one and j minus one to the same recursive function

58
00:04:57,620 --> 00:05:04,220
that we write, but the other possibility for us to arrive at a conclusion that the substring is in

59
00:05:04,220 --> 00:05:09,410
fact is a palindrome is if the substring has just two characters.

60
00:05:09,410 --> 00:05:12,650
So we need to specifically check for this as well.

61
00:05:12,650 --> 00:05:19,220
And that's important because otherwise, as we have seen in the next recursive call, when we increment

62
00:05:19,220 --> 00:05:25,100
I and decrement j, we would get an invalid scenario where j is less than I.

63
00:05:25,130 --> 00:05:29,120
So we have developed the intuition needed for solving this question.

64
00:05:29,120 --> 00:05:35,900
Before we proceed and discuss how we can implement the solutions to this question, let's take a moment

65
00:05:35,900 --> 00:05:39,860
to think about the brute force approach for solving this question.

66
00:05:39,860 --> 00:05:41,960
So what would be the brute force approach?

67
00:05:41,960 --> 00:05:48,080
It would just simply be finding all the possible substrings of the string that is given to us.

68
00:05:48,080 --> 00:05:54,260
And then we would check each substring to identify whether it is a palindrome or not.

69
00:05:54,260 --> 00:05:57,830
And we would just count the number of palindromes that we have got.

70
00:05:57,860 --> 00:06:02,810
Now, what would be the time and space complexity of this approach?

71
00:06:02,810 --> 00:06:09,080
The time and space complexity of this approach would respectively, be of the order of n cube and of

72
00:06:09,080 --> 00:06:12,620
the order of one if we are using an iterative approach.

73
00:06:12,620 --> 00:06:19,040
So that's why space would be constant space, but the time complexity would be of the order of n cube,

74
00:06:19,040 --> 00:06:26,300
because first we would have to find all the substrings and this over here would be an O of N square

75
00:06:26,300 --> 00:06:27,170
operation.

76
00:06:27,170 --> 00:06:33,950
And then we would have to check whether each substring is a palindrome or not, which would be an O

77
00:06:33,950 --> 00:06:35,240
of n operation.

78
00:06:35,240 --> 00:06:41,960
And that's because in the worst case, a substring can be as long as the string which is given to us.

79
00:06:41,960 --> 00:06:47,960
So that's why checking if a substring is a palindrome or not is going to be, in the worst case, an

80
00:06:47,960 --> 00:06:49,430
O of n operation.

81
00:06:49,430 --> 00:06:57,200
And therefore this approach is going to have a time complexity of the order of n square into n, which

82
00:06:57,200 --> 00:06:59,690
is equal to n cube.

83
00:07:00,920 --> 00:07:04,130
Now, this is definitely not a great time complexity.

84
00:07:04,160 --> 00:07:11,240
Let's discuss in the next videos better approaches than the brute force approach for solving this question.