1
00:00:00,700 --> 00:00:07,060
In this video, let's get started with another interesting coding interview question, which is called

2
00:00:07,060 --> 00:00:08,800
palindromic substrings.

3
00:00:09,250 --> 00:00:17,080
So the question reads given a string s, return the number of palindromic substrings in it.

4
00:00:17,680 --> 00:00:23,140
A string is a palindrome when it reads the same backward as forward.

5
00:00:23,290 --> 00:00:28,150
A substring is a contiguous sequence of characters within the string.

6
00:00:28,150 --> 00:00:30,460
You will not be given an empty string.

7
00:00:30,460 --> 00:00:34,810
So this is the question at hand, and we are given an example over here.

8
00:00:34,810 --> 00:00:42,340
If the string that is given to us is a, a, b a, then the output that is required of us is six, which

9
00:00:42,340 --> 00:00:46,360
represents these six substrings which are palindromes.

10
00:00:46,360 --> 00:00:53,470
So the question says again we are given a string s and we have to return the number of palindromic substrings,

11
00:00:53,470 --> 00:00:56,020
which in this case is equal to six.

12
00:00:56,020 --> 00:01:03,880
The question also notice defines what a palindrome is and it also defines what a substring is.

13
00:01:03,880 --> 00:01:08,800
Now again, a substring is a contiguous sequence of characters within the string.

14
00:01:08,800 --> 00:01:11,110
So if you have a a, b a.

15
00:01:12,400 --> 00:01:18,310
This over here is a substring, or this over here is a substring because these are contiguous sequences

16
00:01:18,310 --> 00:01:20,020
of characters within the string.

17
00:01:20,020 --> 00:01:23,290
But again notice you can't omit characters in between.

18
00:01:23,290 --> 00:01:30,220
So for example a, a, b a is the string that is given to you and you can't omit B and say a a a is

19
00:01:30,220 --> 00:01:32,500
a substring because this is not a substring.

20
00:01:32,500 --> 00:01:34,360
This is in fact a subsequence.

21
00:01:34,360 --> 00:01:37,060
But over here we are dealing with substrings.

22
00:01:37,060 --> 00:01:38,680
So let's continue.

23
00:01:38,680 --> 00:01:45,640
An important thing to notice in this question is that over here you have a a B a.

24
00:01:45,640 --> 00:01:51,370
And the question says that this a over here and this a over here alone.

25
00:01:51,370 --> 00:01:55,270
These two are separate palindromic substrings.

26
00:01:55,270 --> 00:01:57,340
So this is something that you should note.

27
00:01:57,340 --> 00:01:59,860
We are not saying that this is an A and this is an A.

28
00:01:59,860 --> 00:02:04,180
And so these two are equal and therefore we will not count duplicates.

29
00:02:04,180 --> 00:02:05,920
So that's not what the question says.

30
00:02:05,920 --> 00:02:10,720
The question clearly says that these are treated as different substrings.

31
00:02:10,990 --> 00:02:12,970
Now we have understood the question.

32
00:02:12,970 --> 00:02:14,350
So we are given a string.

33
00:02:14,350 --> 00:02:18,400
And we need to identify all the palindromic substrings in it.

34
00:02:18,400 --> 00:02:20,470
Now again let's take a look at the example.

35
00:02:20,470 --> 00:02:23,050
Over here we have a a b a.

36
00:02:23,080 --> 00:02:25,990
So that's this a this a b and a.

37
00:02:25,990 --> 00:02:28,900
So these are substrings of length one.

38
00:02:28,900 --> 00:02:31,840
And then you have a a because this is a palindrome.

39
00:02:31,840 --> 00:02:37,330
So you have a A over here and you don't have any other palindrome which is of length two.

40
00:02:37,330 --> 00:02:40,840
And then we have a b a b a is also a substring.

41
00:02:40,840 --> 00:02:42,790
And this in fact is a palindrome.

42
00:02:42,790 --> 00:02:48,010
So these are the six palindromic substrings of the string a a b a.

43
00:02:48,010 --> 00:02:51,190
And that's why the output over here is six.

44
00:02:51,280 --> 00:02:52,990
So we have understood the question.

45
00:02:52,990 --> 00:02:58,570
Now remember whenever you are presented with a coding interview question, it's very important that

46
00:02:58,570 --> 00:03:02,170
you ask any clarifying questions that you may want to ask.

47
00:03:02,440 --> 00:03:09,520
This is very important because it will help you understand what is exactly asked of you, and it will

48
00:03:09,520 --> 00:03:16,690
also help you clarify any doubts you may have so that you spend your time effectively solving the question.

49
00:03:16,690 --> 00:03:24,430
So a possible question that you could ask for the palindromic substring question is do I need to treat

50
00:03:24,430 --> 00:03:27,520
small case and uppercase letters differently?

51
00:03:27,520 --> 00:03:34,150
Or you could ask, Will I be given strings that have both uppercase and lowercase letters?

52
00:03:34,150 --> 00:03:40,570
Let's say the interviewer replies and says that string s, which is the string that is given to you,

53
00:03:40,570 --> 00:03:43,660
will contain only lowercase letters.

54
00:03:43,660 --> 00:03:49,180
So we have understood the question, and we have asked any clarifying questions that we wanted to ask.

55
00:03:49,180 --> 00:03:52,810
Let's now proceed and come up with a few test cases.

56
00:03:52,810 --> 00:03:56,740
Now test cases can be formed together with the interviewer.

57
00:03:56,740 --> 00:04:02,410
It's very helpful if you ask the interviewer whether you could come up with test cases together, because

58
00:04:02,410 --> 00:04:05,500
it will ensure that both of you are on the same page.

59
00:04:05,500 --> 00:04:10,150
Now, in the question itself, we were given a sample test case.

60
00:04:10,150 --> 00:04:18,520
So if the input is a, a, B a, the required output is equal to six because six palindromic substrings

61
00:04:18,520 --> 00:04:21,250
can be formed from this string.

62
00:04:21,250 --> 00:04:28,360
Now, if the string which is given to you is a, b, c, then the output required would be three, because

63
00:04:28,360 --> 00:04:31,300
you can have three palindromic substrings.

64
00:04:31,300 --> 00:04:39,460
Another test case is if you are given the string aa, then also you can form three palindromic substrings.

65
00:04:39,460 --> 00:04:42,220
Again this a and this a alone.

66
00:04:42,220 --> 00:04:47,260
These two cases have to be treated as separate palindromic substrings.

67
00:04:47,260 --> 00:04:51,100
So that's why in this case also the answer is equal to three.

68
00:04:51,100 --> 00:04:57,640
In the next video, let's make a few interesting observations and build the intuition necessary for

69
00:04:57,640 --> 00:04:58,900
solving this question.