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

Answer 2

My C# solution looks for repeated characters in a string and uses them to reduce the number of insertions. In a word like program, I use the 'r' characters as a boundary. Inside of the 'r's, I make that a palindrome (recursively). Outside of the 'r's, I mirror the characters on the left and the right.

Some inputs have more than one shortest output: output can be toutptuot or outuputuo. My solution only selects one of the possibilities.

Some example runs:

• radar -> radar, 0 insertions
• esystem -> metsystem, 2 insertions
• message -> megassagem, 3 insertions
• stackexchange -> stegnahckexekchangets, 8 insertions

First I need to check if an input is already a palindrome:

public static bool IsPalindrome(string str)
{
    for (int left = 0, right = str.Length - 1; left < right; left++, right--)
    {
        if (str[left] != str[right])
            return false;
    }
    return true;
}

Then I need to find any repeated characters in the input. There may be more than one. The word message has two most-repeated characters ('e' and 's'):

private static bool TryFindMostRepeatedChar(string str, out List<char> chs)
{
    chs = new List<char>();
    int maxCount = 1;

    var dict = new Dictionary<char, int>();
    foreach (var item in str)
    {
        int temp;
        if (dict.TryGetValue(item, out temp))
        {
            dict[item] = temp + 1;
            maxCount = temp + 1;
        }
        else
            dict.Add(item, 1);
    }

    foreach (var item in dict)
    {
        if (item.Value == maxCount)
            chs.Add(item.Key);
    }

    return maxCount > 1;
}

My algorithm is here:

public static string MakePalindrome(string str)
{
    List<char> repeatedList;
    if (string.IsNullOrWhiteSpace(str) || IsPalindrome(str))
    {
        return str;
    }
    //If an input has repeated characters,
    //  use them to reduce the number of insertions
    else if (TryFindMostRepeatedChar(str, out repeatedList))
    {
        string shortestResult = null;
        foreach (var ch in repeatedList) //"program" -> { 'r' }
        {
            //find boundaries
            int iLeft = str.IndexOf(ch); // "program" -> 1
            int iRight = str.LastIndexOf(ch); // "program" -> 4

            //make a palindrome of the inside chars
            string inside = str.Substring(iLeft + 1, iRight - iLeft - 1); // "program" -> "og"
            string insidePal = MakePalindrome(inside); // "og" -> "ogo"

            string right = str.Substring(iRight + 1); // "program" -> "am"
            string rightRev = Reverse(right); // "program" -> "ma"

            string left = str.Substring(0, iLeft); // "program" -> "p"
            string leftRev = Reverse(left); // "p" -> "p"

            //Shave off extra chars in rightRev and leftRev
            //  When input = "message", this loop converts "meegassageem" to "megassagem",
            //    ("ee" to "e"), as long as the extra 'e' is an inserted char
            while (left.Length > 0 && rightRev.Length > 0 && 
                left[left.Length - 1] == rightRev[0])
            {
                rightRev = rightRev.Substring(1);
                leftRev = leftRev.Substring(1);
            }

            //piece together the result
            string result = left + rightRev + ch + insidePal + ch + right + leftRev;

            //find the shortest result for inputs that have multiple repeated characters
            if (shortestResult == null || result.Length < shortestResult.Length)
                shortestResult = result;
        }

        return shortestResult;
    }
    else
    {
        //For inputs that have no repeated characters, 
        //  just mirror the characters using the last character as the pivot.
        for (int i = str.Length - 2; i >= 0; i--)
        {
            str += str[i];
        }
        return str;
    }
}

Note that you need a Reverse function:

public static string Reverse(string str)
{
    string result = "";
    for (int i = str.Length - 1; i >= 0; i--)
    {
        result += str[i];
    }
    return result;
}

Answer 3

C# Recursive solution adding to the end of the string:

There are 2 base cases. When length is 1 or 2. Recursive case: If the extremes are equal, then make palindrome the inner string without the extremes and return that with the extremes. If the extremes are not equal, then add the first character to the end and make palindrome the inner string including the previous last character. return that.

public static string ConvertToPalindrome(string str) // By only adding characters at the end
    {
        if (str.Length == 1) return str; // base case 1
        if (str.Length == 2 && str[0] == str[1]) return str; // base case 2
        else
        {
            if (str[0] == str[str.Length - 1]) // keep the extremes and call                
                return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 2)) + str[str.Length - 1];
            else //Add the first character at the end and call
                return str[0] + ConvertToPalindrome(str.Substring(1, str.Length - 1)) + str[0];
        }
    }