Reverse a string O(n/2) time, O(n) space

Reverse a string

We all know how to reverse a string right? But the quest to always find something better than existing algorithms makes us quite excited. But before jumping into the code, let’s try and see the best case i.e.(Ω) for this problem. It will allow us to find out the best possible time we can have to solve the problem. Nothing else faster than that can be achieved.

Algorithm to reverse a string

1. Iterate from beginning of string to n/2 
2. Swap the elements boundary elements 
3. If string is of even length, continue till n/2 and swap that one 
4. Else we let the middle element remain as it is (i.e. continue to (n-1)/2)

This algorithm to reverse a string gives best possible runtime of Ω(n/2). Can we do any better? Looks like not, since we will need to traverse the string halfway anyways. So, if we implement an algorithm to have a Big-O of n/2 as well, then our Θ i.e. average time will also be n/2. That’s a relief, we will have a linear time complexity growth. Our space complexity will always be O(n) since we will not allocate any space and do in-place replacements in the string. I have not been able to find anything else faster than this one. But write in the comments if there is something faster. I am thinking for maybe dynamic programming or multi-threading but we address that in the next post.

Let’s see if I can explain it better. Suppose the string is “ABCDE”. Our loop will iterate 2 times (5/4). In the first iteration, A will be swapped with E. And the 2nd iteration B will be swapped with D. E will remain at its place. So the reversed string will be “EDCBA”. Looks like that is the one we want. Try similar with an even string and it will still be the same.

Now the code! I am using c++ and will use c++14 where possible. Of course we can use the std::reverse as well BUT that one is a time complexity O(n). Check the logic here. The code for our logic is as below:

Cheers,
Naresh

visit me at: https://www.naresh.se/
Follow me on twitter: @wolverine2k

Thanks Naresh for contributing to Algorithms and Me, if you want to contribute, please contact us and refer publishing at Algorithms and Me.