0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Raphael May 1 '17 at 20:14
  • 1
    $\begingroup$ you have to do it for $n$ positions because you have $n$ letters -> this adds factor $n$. $\endgroup$ – 今天春天 May 1 '17 at 20:46
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.