Hi everyone.
Let's discuss various methods by which we can solve this question.
Now let's say that the input string is Malayalam.
All right.
So this is a palindrome.
It reads the same forward and backward.
Now we'll see three methods by which we can solve this.
Now the first method would be that we could create a new string starting from the end.
Right.
We can create a new string.
Initially this string will be empty.
And then we'll take one character by character starting from the end, and we'll append it to the new
string.
And finally, we'll check whether the new string and the given string is the same.
If they are the same, then we return true, else we return false.
So this is one way we can solve this.
Now this is not an optimal solution.
We'll see in in the discussion why this is not optimal.
Now another solution could be that we create an array instead of a new string.
We create initially an array and we take character by character of the given string from the end.
So initially we take character M, then we take character A, etc. and we insert it into the array.
So that would be m, comma a, etc. and then we join these characters to form a string.
And then we compare this string and the given string.
So if they are the same we return true.
If they are not the same, we return false.
So this is another way.
Now this is better than the first method.
And we'll see why that is so.
But it is not the best method.
And finally in this section we'll see a third method where we use two pointers.
And one pointer would be at the beginning.
That's over here.
And the other pointer would be at the end.
And we'll check whether these two have the same character.
And if so, we will increment the beginning pointer to this place over here.
And we'll decrement the pointer at the end to this place.
And we'll keep comparing if they are the same.
So if throughout we get that these characters are the same, we return true, else we break and we return
false.
So these are the three methods that we will discuss.
Now let's go ahead and see the first method where we create a new string.
All right.
So let's say that the input given to us is a b c b a.
Now let's initially create a new string so we can give it any name.
Let's say we call it to check.
All right.
So initially this is an empty string.
Now we have a pointer.
And it's pointing to the end of the given string.
And we take the character at this index.
So this is 01234.
So we take the character at index four which is string length minus one.
Right.
So we take this character and we append it to the.
String which we defined over here to check.
So two check becomes a.
Now it's just a.
Then we move the pointer to the left left right.
So the pointer is pointing over here.
Now that is two index three.
We take the character and we append it to two check.
So two check becomes a b.
So this is string okay.
So again we do the same thing.
We move the pointer to the left and take the character C and append it to two.
Check.
We do it again.
We take the character B and append it to two.
Check.
And we do it again.
We take the character A and append it to two check.
So now we have a new string.
Now we just need to compare these two strings.
Now if they are the same, we can return true because they read the same forward and backward.
And that's the definition of a palindrome.
Now if these two strings are not the same, then we can return false and we have our solution.
Now let's quickly look at the complexity analysis of this solution.
Now the time complexity of this solution will be O of n square.
Why is that.
So you can see that we are doing appending operation on a string right now.
Strings in languages such as JavaScript are immutable.
So when you append something to a string in JavaScript, you are actually traversing the string and
you are creating a new copy of the string and appending the character which you are appending, right?
So this is actually an operation n or order of n operation.
So over here we are doing this every time we have a character.
Right.
So if you have n characters so let's say the string is of length n.
And for each of these when we append we are doing an o of n operation.
So that's why the time complexity over here is n into n, which is o of n square.
So every time we are creating a new string, because strings are immutable in languages like JavaScript.
Remember when we are appending to the string, what's actually happening is we are iterating through
all the characters, copying it, creating a new copy, and adding the new character.
So that's why the time complexity over here is O of n square.
Now what about the space complexity?
The space complexity of this solution is O of N.
Why is that so?
Because we are creating a new string over here, right.
Which is of length n also.
So the space complexity is O of n.