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

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 .

*Any* string? Or some specific one? Did it refer to some code, or just in theory? — Eugene Sh., May 19 '17 at 20:50
there was an input "abcdefghi" and an output "ihgfedcba" , what if Any or specific one ? @EugeneSh. — roy, May 19 '17 at 20:53
Maybe the size of the string is 2. It maybe the string is a palindrome. — RoiHatam, May 19 '17 at 20:53
^Ditto. But given your strings it looks like @Lashane guess is correct. — Eugene Sh., May 19 '17 at 20:54
If you define a string as a contiguous sequence of bytes, then reversing the string is simply a matter of changing the definition of the order in which the sequence occurs. — William Pursell, May 19 '17 at 20:55
For O(1) space complexity, swap the first and last characters, and work your way inward to the middle of the string. This requires extra storage of just a single character to perform the swap. — cdhowie, May 19 '17 at 20:56
But you still need to find the end of the string, so unless you are given the length, it's still O(n) — William Pursell, May 19 '17 at 20:56
With no other details, and assuming "a single operation" means CPU instruction not "a single function call" of something in the stdlib of the language of choice... I don't see any way it's possible to reverse an arbitrary string in O(1) time. O(1) space, certainly, by swapping chars as @cdhowie mentioned. — Adrian, May 19 '17 at 20:56
@WilliamPursell Most languages (C being a notable exception) offer a canonical string type that does know its own length. — cdhowie, May 19 '17 at 20:56
@Adrian I can think of swapping the address lines in the physical memory chip :) — Eugene Sh., May 19 '17 at 20:59
another guess - probably interviewer meant "how would you implement string class the way that reverse is o(1) runtime?" - then the answer is "store char array with string, length, bit flag to indicate direction, so in such implementation reverse is O(1) space/time" — Iłya Bursov, May 19 '17 at 20:59
Oh wait. What about [this one](http://stackoverflow.com/questions/43943699/why-does-this-code-written-backwards-print-hello-world/43943948#43943948)? — Eugene Sh., May 19 '17 at 21:05
@EugeneSh. good finding, but you need to "prepend" your string with this symbol, which means O(N) because of copy :( but if you store strings always with LTR/RTR mark at the beginning - then it is actually o(1) :) — Iłya Bursov, May 19 '17 at 21:06
You can reverse a XOR-linked list in constant time, so if you represent a string a XOR-linked list of chars.. — harold, May 19 '17 at 21:09
@harold ... and plenty of other even simpler data structures designed to reverse in O(1) :) — Eugene Sh., May 19 '17 at 21:10
@harold What about a data structure containing both the "original" string and "reversed" one? — Eugene Sh., May 19 '17 at 21:19
@EugeneSh. no, seriously, there are probably lots of interesting tricks here so why not post them? Well, hopefully more interesting than just keeping track of the reversed version all along, which I wouldn't really count as a data structure and more as an ad-hoc trick, but it's a useful technique — harold, May 19 '17 at 21:26
@harold despite storing length somewhere with the string itself, you can just store pointers to the first/last symbols, use ordinary double linked list, use stack, treemap even — Iłya Bursov, May 19 '17 at 21:30
@harold Why not a data structure? These tricks are used pretty widely. Like have the same data in both min-heap and a binary tree, for example. To benefit from both O(log(n)) searching and O(1) finding the minimum (well, with pointers it can be the same data). — Eugene Sh., May 19 '17 at 21:31
@EugeneSh. yes and I would not typically count them as new data structures either, but as two data structures used in tandem. But that's just terminology. — harold, May 19 '17 at 21:34

score 6 · Answer 1 · edited Feb 01 '20 at 16:51

6

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).

edited Feb 01 '20 at 16:51

Adam Prax

6,413
3
30
31

answered May 19 '17 at 20:57

Pavel P

15,789
11
79
128

1

Who said "one line"? – Eugene Sh. May 19 '17 at 20:58
It's not an answer to the the question. – RoiHatam May 19 '17 at 20:58
It is a single operation (one part of the question) but not O(1) (the other part of the question. – Adrian May 19 '17 at 20:59
1

@EugeneSh. I assume "single operation" means exactly that. You cannot reverse a string in one operation. – Pavel P May 19 '17 at 20:59
The concept of computational complexity is unrelated to whatever functions happen to be available in a given language. Otherwise we could imagine a language where everything is O(1). – Digiproc May 20 '17 at 00:28
@Digiproc yes, but why are you saying that? – Pavel P May 20 '17 at 00:31
The original question was, "Can one reverse a string in O(1)?", but the answer you gave was apparently for the question, "How does one reverse a string in C++". The fact that you mention the complexity of your particular algorithm above still does not answer the original question. I commented to point out that your algorithm does not demonstrate anything about the complexity because we don't know how the underlying function works or whether it uses a theoretically optimal algorithm. – Digiproc May 20 '17 at 00:47
@Digiproc well, it's not a mystery what the complexity of this algorithm in general to reverse a sequence, has nothing to do with the implementation. You can go on and question everything if you feel like. By the way if you feel like it, try to come up with implementation that isn't `O(N)`. – Pavel P May 20 '17 at 00:56

Jesper Juhl · Answer 2 · 2017-05-19T21:05:34.063

1

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.

edited May 19 '17 at 21:05

answered May 19 '17 at 20:55

Jesper Juhl

30,449
3
47
70

Which would be O(n) time since it's based on the length of the string. – Adrian May 19 '17 at 20:55
4

"Iterate" doesn't ring like O(1) – Eugene Sh. May 19 '17 at 20:55
I thought of the same thing though it sounds a bit flippant. – R Sahu May 19 '17 at 20:55
3

I don't think this answer is that bad given the question. You need to iterate over the string to print it out anyway, so that shouldn't be included in the calculation. So printing out the string normally is printing `begin()` to `end()`. Printing out the reverse is printing `rbegin()` to `rend()`. So the string was reversed in O(1). – Kevin May 19 '17 at 20:57
@JesperJuhl what would "less than O(1)" even mean? It gets faster the larger the input? Iterating over a string would be O(n). – Adrian May 19 '17 at 20:58
5

I think what Jesper is trying to say is that "reversing a string" can be effectively a no-op, if it can be defined to be interpreting an existing string in reverse. In that case, the string is "reversed" simply by creating a pair of reverse iterators -- not actually moving any characters around in storage, but by creating a view through which the string can be iterated in reverse. – cdhowie May 19 '17 at 21:00
1

@cdhowie you said it better than I could. – Jesper Juhl May 19 '17 at 21:03
But by this reckoning we could say that any computation is simply a matter of how you interpret the input data, and therefore all computation has a complexity of O(0), negating the need for defining computational complexity.. – Digiproc May 20 '17 at 00:31
1

@Digiproc Only in cases where reinterpreting the data in the desired manner has no additional computational cost -- such as iterating a string in reverse. – cdhowie May 21 '17 at 01:33

score 0 · Answer 3 · answered May 19 '17 at 21:00

0

You can't do it. Even if there is some existing function somewhere that does it, internally it will certainly still take O(n). Although technically the complexity for a swapping is O(n) for an even number of characters and O(n-1) for an odd number of characters (so one could "technically" say that swapping a 3-character string is O(1)), each operation is a little more complex because you have to store one swapped character in a local variable while you swap the other. So for practical reasons swapping would be slower, not faster.

answered May 19 '17 at 21:00

Digiproc

215
1
9

3

`O(n - 1)` is exactly the same thing as `O(n)`. And it's `O(1)` for any string of constant length, not just 3. – kraskevich May 19 '17 at 22:21
there is no such thing as `O(N-1)`, it's `O(N)`. If you wanted to calculate how many operations there, it would be `N/2` or `N/2-1` – Pavel P May 20 '17 at 00:35
O(n-1) is more precise than O(n) (for odd number of characters). If, however, you prefer the less precise value, then go right ahead. – Digiproc May 20 '17 at 01:02
3

No, you would fail interview if you insisted that O(N-1) was more precise. Also, it's not N-1 as I pointed out, it's N/2-1 – Pavel P May 20 '17 at 01:15
And why would I want to work at a place that preferred imprecision over precision? – Digiproc May 20 '17 at 10:45
Secondly, computational complexity is an indication of the number of steps, where each step could, in theory, be implemented with one hardware clock cycle (barring multithreading). Ergo, its N-1, not N/2-1. – Digiproc May 20 '17 at 10:49
3

You're using the big-Oh notation improperly. `O(f(n))` denotes a class of functions. Saying that one of two functions that represent the same class is more precise than the other clearly shows that you don't understand what this notation actually means. – kraskevich May 20 '17 at 10:55

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

3 Answers3