In C++ let's check if the string is palindrome in 3 different ways:

**#1 Longer code, but efficient way**

**#2 Little bit shorter code, but not so efficient way**

**#3 The shortest code, but not so efficient way**

I declared the first one as the most efficient, because it does not create a new string, but anyways, after the function is end, it must get deleted from the memory. So you can use the last one if you are not very limited in memory.

**UPD** Adding the 4-th way suggested by Halit and this is the best possible way.

**#4 The shortest code and efficient way**

You can find info about that last one here.

**UPD2** Time complexity was mentioned in the comments. The time complexity is $$$O(n)$$$ for all of those 4 ways. But some of them is at most $$$n/2$$$ operations (comparisons of chars) and some $$$n$$$. If you care about that, you can use the last approach, because I can not modify that 3-rd approach to make it $$$n/2$$$ operations, because getting substring can not be done in $$$O(1)$$$ in C++ unlike Java.

**UPD3** Notice from the 3-rd way when you want to reverse string and keep the original one as well, doing `string t(s.rbegin(), s.rend())`

is better than doing `string t = s`

and then `reverse(t.begin(), t.end())`

. Also when you want to print reversed directly, you can do `cout << string(s.rbegin(), s.rend()) << '\n'`

.

You can do also like that;

Wow, this is probably the best way. I think it does not create a new string?

yes, it doesn't create a new string.

https://en.cppreference.com/w/cpp/algorithm/equal

Wow!

the Time Complexity of the first way is O(n / 2), the others if O(n).

I hate to be that guy but $$$O(\frac{n}{2})$$$ is still $$$O(n)$$$

Yes, as said, those time complexities are same, but I added the answer to this comment (about # of operations) to the blog.

I guess you can also do a polynomial rolling hash for the string and check it that way. The string hashing is completely necessary and totally can't be substituted for naive character by character comparison. Time complexity is $$$O(n)$$$

It is an overkill for a full string check, but efficient for checking many different substrings. So, hashing can solve the longest palindromic substring problem by also using binary search the answer technique.

Auto comment: topic has been updated by alpenglow (previous revision, new revision, compare).