How to reverse a string in O(1) complexity (runtime)? [closed]

Question

I faced an interview today and I was asked to reverse a string in single operation . I was feeling like it is impossible in less than O(n) . By the way , I was given a clue , "Swapping" ! So . . . does any answer exist ?

• Sample Input : "abcdefghi" (or , any strings )
• Sample Output :"ihgfedcba"
• No built in function can be used . ( ex : strrev() )
• The answer is not tricky like just printing/iterating reversely .

Answer 1

You cannot reverse a string in O(1) time, however, you can do so with O(1) space complexity.

reverse a string in single operation

Most likely it was reverse it in one-liner, as it's not even clear what an "operation" is really is.

You can use std::reverse algorithm to reverse a string in one line:

#include <string>
#include <algorithm>

int main()
{
    std::string str = "Hello world!";
    std::reverse(str.begin(), str.end());
    std::cout << "reverse is: \"" << str << '\"' << std::endl;
}

Output:

reverse is: "!dlrow olleH"

or you may as well use a simple loop to do it:

for (size_t i=0; i<str.size()/2; ++i)
    std::swap(str[i], str[str.size()-1-i);

this is however is O(N) runtime, and O(1) space (just like std::reverse).

Usually interviews with simple reverse string algorithm questions isn't about some tricks, most likely your interviewer wanted to see that kind of loop implemented. Also, don't forget that interviewers are also humans and sometimes they simply make mistakes and ask for impossible. Or, they simply wanted you to say that it is not possible to reverse a sequence in O(1).

Answer 2

Reverse a string? Just iterate it from rbegin() to rend(). Or std::copy that range to a new string. A "reversed string" is just the same as the original string, just read the other way.