34. [20] A random binary string of length 1000 is chosen. Let $L$ be the expected length of its longest (contiguous) palindromic substring. Estimate $L$.
An estimate of $E$ will receive $\left\lfloor 20 \min \left(\frac{E}{L}, \frac{L}{E}\right)^{10}\right\rfloor$ points.
Answer:
$$
L \approx 23.120
$$

Solution: The probability that there exists a palindromic substring of length $2 n+1$ is approximately $2^{-n} \cdot 1000$. Thus, we can expect to often see a length 21 palindrome, and sometimes longer ones. This leads to a guess a bit above 21 .
$L$ was approximated with $10^{7}$ simulations (the answer is given with a standard deviation of about $\left.10^{-3}\right)$.