# O(n) Palindromic Substring: Why is O(n^2) needed here?

I have been doing dynamic programming problems, and I came across a palindromic substring question. I answered it quickly, and found an $O(n)$ dynamic programming solution, but when I check the actual solution, I find that I should be getting an $O(n^2)$ result.

Can someone explain where I am going wrong/how this is not correct?

The problem reads: given string $x_1,x_2,\ldots,x_n$, find the longest palindromic substring.

I write:

$$T(i) = \text{max length palindromic substring ending at position }i\text{ in string }X$$

Then I write down the following subproblem (where $j$ is intended to be the letter right before the beginning of the palindrome ending at position $i$):

\begin{align} \text{IF }x_i = x_j, \text{ where } &j = i - T(i-1)-1:\\ T(i) &= T(i - 1) + 2;\\ \text{ELSE IF} x_i = x_{i-1} \\ T(i) &= 2;\\ \text{ELSE } T(i) &=1; \end{align}

As far as I can tell, this is correct. In order to recover the palindrome, I record it in linked lists or whatever, and calculate the argmax of $T$.

Where am I going wrong?

• Without checking if you made a mistake: the fact that there is a quadratic-time algorithm does not imply that there is no linear-time algorithm. – Raphael May 1 '17 at 20:14
• you have to do it for $n$ positions because you have $n$ letters -> this adds factor $n$. – 今天春天 May 1 '17 at 20:46

Consider the following string $$dabacabac$$ When you go to compute $T(9)$ (using one indexing), you have $T(8) = 7$. But since $$T(1) = d \neq c = T(9)$$ You will put $T(9) = 1$, when it should be $T(9) = 5$.