In this video, let's get started with another interesting coding interview question, which is called
palindromic substrings.
So the question reads given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
You will not be given an empty string.
So this is the question at hand, and we are given an example over here.
If the string that is given to us is a, a, b a, then the output that is required of us is six, which
represents these six substrings which are palindromes.
So the question says again we are given a string s and we have to return the number of palindromic substrings,
which in this case is equal to six.
The question also notice defines what a palindrome is and it also defines what a substring is.
Now again, a substring is a contiguous sequence of characters within the string.
So if you have a a, b a.
This over here is a substring, or this over here is a substring because these are contiguous sequences
of characters within the string.
But again notice you can't omit characters in between.
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
a substring because this is not a substring.
This is in fact a subsequence.
But over here we are dealing with substrings.
So let's continue.
An important thing to notice in this question is that over here you have a a B a.
And the question says that this a over here and this a over here alone.
These two are separate palindromic substrings.
So this is something that you should note.
We are not saying that this is an A and this is an A.
And so these two are equal and therefore we will not count duplicates.
So that's not what the question says.
The question clearly says that these are treated as different substrings.
Now we have understood the question.
So we are given a string.
And we need to identify all the palindromic substrings in it.
Now again let's take a look at the example.
Over here we have a a b a.
So that's this a this a b and a.
So these are substrings of length one.
And then you have a a because this is a palindrome.
So you have a A over here and you don't have any other palindrome which is of length two.
And then we have a b a b a is also a substring.
And this in fact is a palindrome.
So these are the six palindromic substrings of the string a a b a.
And that's why the output over here is six.
So we have understood the question.
Now remember whenever you are presented with a coding interview question, it's very important that
you ask any clarifying questions that you may want to ask.
This is very important because it will help you understand what is exactly asked of you, and it will
also help you clarify any doubts you may have so that you spend your time effectively solving the question.
So a possible question that you could ask for the palindromic substring question is do I need to treat
small case and uppercase letters differently?
Or you could ask, Will I be given strings that have both uppercase and lowercase letters?
Let's say the interviewer replies and says that string s, which is the string that is given to you,
will contain only lowercase letters.
So we have understood the question, and we have asked any clarifying questions that we wanted to ask.
Let's now proceed and come up with a few test cases.
Now test cases can be formed together with the interviewer.
It's very helpful if you ask the interviewer whether you could come up with test cases together, because
it will ensure that both of you are on the same page.
Now, in the question itself, we were given a sample test case.
So if the input is a, a, B a, the required output is equal to six because six palindromic substrings
can be formed from this string.
Now, if the string which is given to you is a, b, c, then the output required would be three, because
you can have three palindromic substrings.
Another test case is if you are given the string aa, then also you can form three palindromic substrings.
Again this a and this a alone.
These two cases have to be treated as separate palindromic substrings.
So that's why in this case also the answer is equal to three.
In the next video, let's make a few interesting observations and build the intuition necessary for
solving this question.