That's not O(1), that's O(log n) memory, where `n` is the size of your string. You need `log n` bits to store the pointer. Granted, it's very limited for practi

That's not O(1), that's O(log n) memory, where `n` is the size of your string. You need `log n` bits to store the pointer. Granted, it's very limited for practical purposes, but you have to account for it in theoretical applications. UPD: you can also say that you're actually writing a code for a Turing machine with two heads, and that would be ok. So, yeah, this is why the "you cannot write a constant-memory algorithm" definition is very hand-waving, one has to be extra careful with the model they're working in.