Rotate the string in O(n) time and O(1) space
An animated algorithm, with 0 lines of code
Let’s consider a classic algorithmic problem — string rotation. Given a string and offset, we should return the rotated string. That is for “Matrix” and offset equal to two the result would be “ixMatr”:
The fastest way to do it seems to be to move each character to its final place. That way, we spend the absolute minimum required amount of actions to get the result.
However, if we would try to do that we could run into an issue:
When a character is moved to its destination, it overwrites the original character, and the result string is incorrect.
To solve it we would need to move our characters to a newly created empty string of the right size:
It’s a good method, but it has an obvious drawback: it requires an extra space (and there is also time that is needed to allocate that space).
One small optimization that could be applied here is to create space only for suffix:
It’s better in practice (e.g., imagine rotating 16777214-char long string to two characters), but asymptotically it’s still O(n). Can we do better?
We can if we sacrifice speed. If instead of storing the whole suffix we store just one character then it would be O(1) extra space:
The downside is that it’s way worse in run time with O(n²). Is it possible to have O(n) run time with O(1) extra memory?
If we would look at the very first attempt to do the rotation in-place, we could notice the problem: we were overwriting characters. What if instead of moving characters sequentially, we would next move the character we are about to overwrite? It could actually work:
But not always:
It’s not impossible to solve this issue, e.g., we could remember which character has already been rotated, but the implementation would be quite complex, and such a solution would require extra O(n) space (although booleans, not chars). We already have a far simpler and quite efficient algorithm with O(n) extra space.
But the way to rotate the string in O(n) run time and O(1) extra space does actually exist.
It is described in a “Programming Pearls” book, and it is very smart. The book author Jon Bentley gives it as an example of aha! moment, though it’s unlikely I would be able to think of something like this on my own:
- Reverse the prefix
- Reverse the suffix
- Reverse the whole word
It isn’t intuitive, but it does work:
It moves each character twice, so in practice, it might run slower than the copy algorithm, but asymptotically it is O(n), and it uses O(1) extra space.
