algorithm - 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

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