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 } &amp;j = i - T(i-1)-1:\\
T(i) &amp;= T(i - 1) + 2;\\
\text{ELSE IF} x_i = x_{i-1} \\
T(i) &amp;= 2;\\ 
\text{ELSE } T(i) &amp;=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?
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$.