How can I compute the number of characters required to turn a string into a palindrome?

Question

I recently found a contest problem that asks you to compute the minimum number of characters that must be inserted (anywhere) in a string to turn it into a palindrome.

For example, given the string: "abcbd" we can turn it into a palindrome by inserting just two characters: one after "a" and another after "d": "adbcbda".

This seems to be a generalization of a similar problem that asks for the same thing, except characters can only be added at the end - this has a pretty simple solution in O(N) using hash tables.

I have been trying to modify the Levenshtein distance algorithm to solve this problem, but haven't been successful. Any help on how to solve this (it doesn't necessarily have to be efficient, I'm just interested in any DP solution) would be appreciated.

Answer 1

Seems like you could solve this simply by working from the ends inward - if the two outer characters don't match, then you'll need to add a character next to one of those that matches the other; then move your focus onto the next pair of non-matching characters, until you've worked your way to the middle of the string and your area of examination contains no characters.

Seems like a fairly straightforward O(n) algorithm to me, since you always move one of your "examination window" boundaries inwards by at least one step with every iteration, and thus you're guaranteed to finish by a maximum of n iterations.

There are actually multiple solutions for your example string,

abcbd -> adbcbda, or abcbd -> dabcbad

both of which are edit distance 2.

The former would come if you decided to add an a to balance out the initial a<>d inequality first; the latter would come if you decided to add a d first. To make sure the solution is optimal, however, you'd probably need to examine the "next letter in" past the two you're currently comparing; if one of the "next letters in" can provide a match for half of your comparison, then you favor adding a match for the other to allow the existing match to remove more characters.

Answer 2

Note: This is just a curiosity. Dav proposed an algorithm which can be modified to DP algorithm to run in O(n^2) time and O(n^2) space easily (and perhaps O(n) with better bookkeeping).

Of course, this 'naive' algorithm might actually come in handy if you decide to change the allowed operations.

---

Here is a 'naive'ish algorithm, which can probably be made faster with clever bookkeeping.

Given a string, we guess the middle of the resulting palindrome and then try to compute the number of inserts required to make the string a palindrome around that middle.

If the string is of length n, there are 2n+1 possible middles (Each character, between two characters, just before and just after the string).

Suppose we consider a middle which gives us two strings L and R (one to left and one to right).

If we are using inserts, I believe the Longest Common Subsequence algorithm (which is a DP algorithm) can now be used the create a 'super' string which contains both L and reverse of R, see Shortest common supersequence.

Pick the middle which gives you the smallest number inserts.

This is O(n^3) I believe. (Note: I haven't tried proving that it is true).