Hi everyone.
Let's now discuss the third method to solve this question.
Now let's say that the input string is a b, c b a.
Now what we'll do is we'll have two pointers one at the beginning of the input string and the other
pointer at the end of the input string.
Now we'll check whether the characters at these two pointers are the same.
Now in this case we have a and a.
Now if the characters are the same or equal then we will proceed or else we can stop.
Right?
If the if these two are different, then definitely the input string is not a palindrome, right?
So if they are not the same then we stop and we return false.
Now what we do if they are, if they are the same, what do we do?
We have the input string over here.
We shift the pointer.
The left pointer is shifted to the right.
We do I plus plus and the right pointer is shifted to the left.
We do j minus minus.
So our pointers are at these positions now.
And again we check whether these are the same.
If they are not the same we return false.
If they are the same we proceed again we move the pointers.
Now at this point you can see that both the pointers are pointing to the same character.
So definitely they will be the same.
And we can stop, right?
We can stop.
And we found that the answer is true and we return true.
Now there could be also another case over here.
You can see that the length of this string is odd right?
It's five five characters the length.
Now let's say it was even like a b c, c b a.
In this case what would happen now we initially have the pointers here and here.
Then we move them to here and here.
And afterwards we move the pointers to these two places.
Now they are the same.
Now in the next iteration you can see that the pointers come like this.
Right.
J comes over here because we move it to the left.
And I comes here because we move I to the right.
Now at this point you can see that J is bigger right.
So we we need to stop.
Right.
So we need to continue this iteration only as long as I is less than or equal to J.
So that's the point which I want you to take away from this.
Or you can say that as long as I is not greater than J, both are the one and the same.
All right.
So in this way we can just use two pointers and we can solve this problem.
Now let's quickly look at the complexity of this solution.
Now what about the time complexity.
The time complexity of this solution is O of n.
Why is that?
So we are just traversing the given array once, right?
In fact, we could say that it is o of n by two because we are traversing it from both the sides right
with I and j.
But then one by two is a constant.
So we can just remove that and we get that.
The time complexity of this solution is O of n.
Now what about the space complexity?
That's the interesting thing of this solution.
The space complexity of this solution is O of one.
Why is that so?
Because we are not using any additional space, right?
We are just having two pointers and we are just comparing the values that are there in these two pointers.
So it does not scale whether the input string is of length five or 5000 or 5 million.
We are just using these two pointers and we are traversing the given string once.
So the space complexity of this solution is O of one.
So we have discussed these three methods for finding whether the given string is a palindrome or not.
The first method was creating a new string and then comparing.
And we saw that the time complexity of this solution is O of n square, and the space complexity is
O of n.
The second solution was better than the first.
Instead of creating an empty new string, we created a new array and we kept pushing to the array,
and at the end we converted that array to a string.
And then we compared.
Now in this case, we found that the time complexity was O of n and the space complexity was O of n.
So compared to the first method, we improved upon the time complexity.
Now in the third method that we discussed, we had two pointers pointing at the beginning and the end.
And then we kept moving them right.
We did beginning plus, plus and end minus minus or moving the beginning pointer to the right and the
end pointer to the left.
And we kept checking whether the characters were the same at these two pointers.
And for this solution we saw that the time complexity is O of n and the space complexity is O of one.
And this is the optimum solution for this question.