How to compute palindrome from a stream of characters in sub-linear space/time?
Posted
by
wrick
on Stack Overflow
See other posts from Stack Overflow
or by wrick
Published on 2011-02-10T22:40:50Z
Indexed on
2011/02/10
23:25 UTC
Read the original article
Hit count: 224
I don't even know if a solution exists or not. Here is the problem in detail. You are a program that is accepting an infinitely long stream of characters (for simplicity you can assume characters are either 1 or 0). At any point, I can stop the stream (let's say after N characters were passed through) and ask you if the string received so far is a palindrome or not. How can you do this using less sub-linear space and/or time.
© Stack Overflow or respective owner