Proof for Minimum number of insertions to convert a string to a palindrome

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

• 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?
– D.W.
Jan 28 '16 at 20:03

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