[IOI 2000] Palindrome

This problem would have been a classical problem if the memory limits would not have been that tight. In the classical version we can use DP or the LCS with O(n^2) memory but this problem requires O(n) memory.

How to go about it?

I searched the solution of this problem online but found only codes and not the solution.