Hi everyone.
Let's now discuss the second method to solve this question.
We have seen that when we created a new empty string, right?
And then we kept on appending the characters to it from the back we went in this direction.
This is the given string.
It had a time complexity of O of n square, because appending to a string is not a constant time operation,
it's a o of n operation.
Right.
So we've seen that.
So that's why this was not efficient.
So let's make a slight tweak to method one.
And instead of having initially an empty string let's have an empty array over here.
All right.
Now instead of appending we will keep pushing the characters from the end of the given string.
And so initially we will take a and we will push it to the empty array.
And then we'll take the next character from the left which is B.
We'll push it.
So two check will become this array over here.
Right.
So this A is over here.
This B is over here.
This C is over here.
And then we take this b we push it to the array.
And then we take this a and we push it to this array.
So two check becomes this array over here.
Now after this what we do is we use a join function to convert this array into a string.
Right.
So we convert it into a string a b c b a.
And then we check this string and the given string.
This is the given string.
And we check this string.
If they are the same we return true.
If they are not the same, we return false.
So this is much better than the previous solution.
Let's look at the complexity of this solution.
What about the time complexity?
We can see that this has just a time complexity of O of n.
The previous solution had a time complexity of O of n square.
Now why is there such a drastic difference over here?
We are pushing to the array right now.
Pushing an element to an array is a constant time operation.
So this is not costing us time, right?
We are just traversing the given string once, which is an O of n operation.
Right.
So that's why the time complexity of this solution is O of n.
Now what about the space complexity?
The space complexity is also O of n because we are creating a new array.
Right.
And and we we have that array over here.
Right.
So again the space complexity over here is also O of n.
Notice that this this new array which we created, the same array we are converting to a string.
Right.
So again the space we are just taking extra space to create this array.
And then we are converting that same array into a string.
So the space complexity of this solution is O of n.