  We consider computing a longest palindrome in the streaming model, where the
symbols arrive one-by-one and we do not have random access to the input. While
computing the answer exactly using sublinear space is not possible in such a
setting, one can still hope for a good approximation guarantee. Our
contribution is twofold. First, we provide lower bounds on the space
requirements for randomized approximation algorithms processing inputs of
length $n$. We rule out Las Vegas algorithms, as they cannot achieve sublinear
space complexity. For Monte Carlo algorithms, we prove a lower bounds of
$\Omega( M \log\min\{|\Sigma|,M\})$ bits of memory; here $M=n/E$ for
approximating the answer with additive error $E$, and $M= \frac{\log n}{\log
(1+\varepsilon)}$ for approximating the answer with multiplicative error $(1 +
\varepsilon)$. Second, we design three real-time algorithms for this problem.
Our Monte Carlo approximation algorithms for both additive and multiplicative
versions of the problem use $O(M)$ words of memory. Thus the obtained lower
bounds are asymptotically tight up to a logarithmic factor. The third algorithm
is deterministic and finds a longest palindrome exactly if it is short. This
algorithm can be run in parallel with a Monte Carlo algorithm to obtain better
results in practice. Overall, both the time and space complexity of finding a
longest palindrome in a stream are essentially settled.
