3
$\begingroup$

For the problem "Find the minimum number of insertions to convert a string $S$ to a palindrome", a recurrence relation usually given is:

$$ c[i,j] = \begin{cases} c[i+1,j-1] & \text{if } S[i] = S[j], \\ \min(c[i+1,j],c[i,j-1]) + 1 & \text{otherwise}. \end{cases} $$

(where $c[i,j]$ denotes the minimum insertions for the substring of $S$ beginning with index $i$ and ending with $j$).

But how do we (formally) prove the correctness of that relation? I tried to use the "cut-and-paste" method, but wasn't sure how to apply it here (to either the first or second line of the recurrence relation).

$\endgroup$
  • 2
    $\begingroup$ Same as how you prove any recursive algorithm correct: By induction. What have you tried? Have you tried proof by induction? Where did you get stuck? $\endgroup$ – D.W. Jan 28 '16 at 20:03
3
$\begingroup$

As D.W. indicates, you use proof by induction. I'll explain this with some hints on the case $S[i] = S[j]$. The intuition is that if $S[i] = S[j]$ then the best way of converting $S[i],\ldots,S[j]$ into a palindrome is converting $S[i+1],\ldots,S[j-1]$ into one, and then converting this to a solution for $S[i],\ldots,S[j]$ at no further cost (how?).

Formally, we need to prove two things:

  1. $c[i,j] \leq c[i+1,j-1]$.
  2. $c[i,j] \geq c[i+1,j-1]$.

For the first inequality, you need to show that if you can convert $S[i+1],\ldots,S[j-1]$ into a palindrome by inserting $m$ characters, then you can convert $S[i],\ldots,S[j]$ into a palindrome by inserting at most $m$ characters. You get the first inequality by taking $m = c[i+1,j-1]$. The proof is not difficult and left to you.

The second inequality is more delicate. Now you need to show that if you can convert $S[i],\ldots,S[j]$ into a palindrome by inserting $m$ characters then you can convert $S[i+1],\ldots,S[j-1]$ into a palindrome by inserting at most $m$ characters. To show this, consider the insertions converting $S[i],\ldots,S[j]$ into a palindrome: $$ w_{i-1},S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j],w_j. $$ Here the $w_t$'s are words which may be empty.

Claim: We can modify this solution to a solution with possibly less insertions in which at least one of $w_{i-1},w_j$ is empty.

(Proof left to you.) If both $w_{i-1},w_j$ are empty then it is easy to complete the proof (details left to you). Otherwise, suppose without loss generality that $w_j$ is empty, that is, the insertions are

$$ w_{i-1},S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j]. $$

Since $w_{i-1}$ is non-empty and the word is a palindrome, it must start with $S[j]=S[i]$. Writing $w_{i-1} = S[j] x$, we can rewrite this solution as

$$ S[i],x,S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j]. $$

I'll let you finish the proof of this case from here, and to mimic this proof for the case $S[i] \neq S[j]$.

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