In this video, let's try to make a few interesting observations, and this will help us build the intuition
necessary to come up with the approach for solving the palindromic substrings question.
So for this, let's take a look at a few cases.
Let's say the string that is given to us is either a b a or a b b a.
We in either of these cases can see that the first character and the last character are equal, and
if that is the case, then we would have to check the remaining string.
So in this case that would be this part.
And in this case that would be this part.
To understand whether the whole string is a palindrome or not, let's say the pointer that is pointing
to this character is I, and the pointer that's pointing to the last character is J.
And that's the case over here as well.
Now for identifying the remaining part of the string.
Notice that the pointers I and J would be pointing to I plus one and j minus one, which would help
us to identify the remaining part of the string.
Now let's take another case.
Let's say the string that is given to us is AA ba.
Now over here again we see that a and A are equal.
But when we check the remaining part of the string, we see that it's not a palindrome.
And we can conclude that a, a, b a is not a palindrome.
But because in this question we need to identify all palindromic substrings.
Therefore, we can't just stop at this, but rather we would need to still check the substring a, b
a, and we would in fact find a palindrome over here.
So if I were pointing at this character and if J were pointing at this character to identify this substring,
we would have to only increment I and keep j where it is itself.
So this substring over here is represented by I plus one and j itself.
In a similar manner.
If the string given to us where a, b a a, even though these two are equal, and we see that the remaining
string is not a palindrome, we can't stop there.
We would also need to check this substring over here, which is given by I remaining where it was,
but j changing from j to j minus one.
So what we have learned over here is that to identify all the possible palindromic substrings we have
to do three checks.
So that's one check over here which is I plus one and J minus one.
And the second case would be I plus one j and I j minus one.
Now this over here will help us to identify whether the substring that we are considering, which is
from I to J, is a palindrome or not.
But these two calls over here will help us to identify other possible substrings by just moving one
of the indices at a time when we implement the code for this, we would achieve these three checks by
just using recursive calls for it.
Now let's make a few more interesting observations.
So for this let's make some space.
Now think of the case that you are given a string which just has one character.
Let's say it's just a now this character or this string is a palindrome.
And notice that for identifying this, we just need to check whether the two pointers are pointing at
the same character.
So if I and J which are the two pointers that we will use, if these two are pointing at the same character,
then this substring is definitely a palindrome.
Another interesting observation that we can make is let's say the string that we are considering is
AA.
So it just has two characters and I is pointing at A and j is pointing also at a.
So these two are equal.
Now basis what we have discussed over here we would increment I and decrement j.
But if we do that j would become less than I, which is not a valid case because I is the starting index
and j is the ending index.
And j always has to be greater than or equal to I.
So to avoid this type of a scenario, if we see that the characters at index I and j are equal, not
only do we need to check the case where we pass I plus one and j minus one to the same recursive function
that we write, but the other possibility for us to arrive at a conclusion that the substring is in
fact is a palindrome is if the substring has just two characters.
So we need to specifically check for this as well.
And that's important because otherwise, as we have seen in the next recursive call, when we increment
I and decrement j, we would get an invalid scenario where j is less than I.
So we have developed the intuition needed for solving this question.
Before we proceed and discuss how we can implement the solutions to this question, let's take a moment
to think about the brute force approach for solving this question.
So what would be the brute force approach?
It would just simply be finding all the possible substrings of the string that is given to us.
And then we would check each substring to identify whether it is a palindrome or not.
And we would just count the number of palindromes that we have got.
Now, what would be the time and space complexity of this approach?
The time and space complexity of this approach would respectively, be of the order of n cube and of
the order of one if we are using an iterative approach.
So that's why space would be constant space, but the time complexity would be of the order of n cube,
because first we would have to find all the substrings and this over here would be an O of N square
operation.
And then we would have to check whether each substring is a palindrome or not, which would be an O
of n operation.
And that's because in the worst case, a substring can be as long as the string which is given to us.
So that's why checking if a substring is a palindrome or not is going to be, in the worst case, an
O of n operation.
And therefore this approach is going to have a time complexity of the order of n square into n, which
is equal to n cube.
Now, this is definitely not a great time complexity.
Let's discuss in the next videos better approaches than the brute force approach for solving this question.