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

Question

Today I came across an interview, and I was asked to change the line in a single operation . I felt this was not possible in less than O (n) . By the way, they gave me the key: " Swap "! So., Is there any answer?

• Input Example: "abcdefghi" (or any lines)
• Output Example: "ihgfedcba"
• You cannot use the built-in function. ( strrev() : strrev() )
• The answer is not complicated, as just printing / iterating back.

Answer 1

You cannot change the line in O(N) , but you can do it with O(1) space complexity.

return line in one operation

Most likely it was reverse it in one-liner , since he did not even understand what an “operation” really is.

You can use std :: reverse to reverse the line 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 can use a simple loop for this:

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

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

Usually, interviews with simple inverse string algorithm algorithms are not about some tricks; most likely, your interviewer wanted to see that such a cycle has been implemented. Also, do not forget that interviewers are also people, and sometimes they just make mistakes and ask for impossibility. Or they just wanted you to say that it is not possible to change the sequence in O(1) .

Answer 2

Invert string? Just translate it from rbegin () to rend() . Or std::copy , which range from a new line. An "inverted line" is the same as the original line, just read the other way.

Answer 3

You cannot do this. Even if there is some existing function somewhere that does this, internally it will certainly still accept O (n). Although technically the difficulty for swapping is O (n) for an even number of characters and O (n-1) for an odd number of characters (so you can technically say that replacing a 3-character string is O (1)), each operation is a bit harder because you have to store one changed character in a local variable while you change another. Therefore, for practical reasons, the exchange will be slower, and not faster.