How to get the shortest palindrome of a string

Question

For example :

String is : abcd

shortest palindrome is abcdcba is the solution

longer palindrome can be : abcddcba

another example:

String : aaaab

shortest palindrome is aaaabaaaa

longer palindrome can be aaaaabbaaaa

Restrictions : you can only add characters in the end.

Answer 1

    using System;
    using System.Collections.Generic;
    using System.Linq;
    public class Test
    {

    public static void shortPalindrome(string [] words){
    List<string> container = new List<string>(); //List of Palindromes

    foreach (string word in words )
    {
        char[] chararray = word.ToCharArray();
        Array.Reverse(chararray);
        string newText = new string(chararray);

        if (word == newText) container.Add(word); 
    }

    string shortPal=container.ElementAt(0);
    for(int i=0; i<container.Count; i++)
    {
        if(container[i].Length < shortPal.Length){
            shortPal = container[i];
        }

    }

    Console.WriteLine(" The Shortest Palindrome is {0}",shortPal);

    }

    public static void Main()
    {
    string[] word = new string[5] {"noon", "racecar","redivider", "sun", "loss"};
    shortPalindrome(word);
    }
    }

Answer 2

It looks like the solutions outlined here are O(N^2) (for each suffix X of the reversed string S, find if S + X is a palindrome).

I believe there is a linear, i.e O(N) solution for this problem. Consider the following statement: the only time where you would append less characters than S.Length - 1 is when the string already contains a partial palindrome, so it will be in the form of NNNNNPPPPPP, where PPPPP represent a palindrome. This means that if we can find the largest trailing palindrome, we can solve it linearly by concatenating the reverse of NNNNN to the end.

Finally, there exists a famous algorithm (Manacher, 1975) that finds the longest (and in fact, all) of the palindromes contained in a string (there is a good explanation here). It can be easily modified to return the longest trailing palidrome, thus giving a linear solution for this problem.

If anyone is interested, here is the full code for a mirror problem (append characters at the beginning):

   using System.Text;

    // Via http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
    class Manacher
    {
        // Transform S into T.
        // For example, S = "abba", T = "^#a#b#b#a#$".
        // ^ and $ signs are sentinels appended to each end to avoid bounds checking
        private static string PreProcess(string s)
        {
            StringBuilder builder = new StringBuilder();

            int n = s.Length;
            if (n == 0) return "^$";

            builder.Append('^');

            for (int i = 0; i < n; i++)
            {
                builder.Append('#');
                builder.Append(s[i]);
            }

            builder.Append('#');
            builder.Append('$');

            return builder.ToString();
        }

        // Modified to return only the longest palindrome that *starts* the string
        public static string LongestPalindrome(string s)
        {
            string T = PreProcess(s);
            int n = T.Length;
            int[] P = new int[n];
            int C = 0, R = 0;
            for (int i = 1; i < n - 1; i++)
            {
                int i_mirror = 2 * C - i; // equals to i' = C - (i-C)

                P[i] = (R > i) ? Math.Min(R - i, P[i_mirror]) : 0;

                // Attempt to expand palindrome centered at i
                while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
                    P[i]++;

                // If palindrome centered at i expand past R,
                // adjust center based on expanded palindrome.
                if (i + P[i] > R)
                {
                    C = i;
                    R = i + P[i];
                }
            }

            // Find the maximum element in P.
            int maxLen = 0;
            int centerIndex = 0;
            for (int i = 1; i < n - 1; i++)
            {
                if (P[i] > maxLen 
                    && i - 1 == P[i] /* the && part forces to only consider palindromes that start at the beginning*/)
                {
                    maxLen = P[i];
                    centerIndex = i;
                }
            }

            return s.Substring((centerIndex - 1 - maxLen) / 2, maxLen);
        }
    }
    
public class Solution {
    public string Reverse(string s)
    {
        StringBuilder result = new StringBuilder();
        for (int i = s.Length - 1; i >= 0; i--)
        {
            result.Append(s[i]);
        }
        return result.ToString();
    }
    

        public string ShortestPalindrome(string s)
        {
            string palindrome = Manacher.LongestPalindrome(s);
            string part = s.Substring(palindrome.Length);
            return Reverse(part) + palindrome + part;
        }
}

Answer 3

Below is my answer for another case: shortest palindrome by attaching characters to the front. So your task is to understand the algorithm and modify it appropriately. Basically, it states that from a string s find the shortest palindrome by adding some characters to the front of s.

If you have never tried to solve this problem, I suggest that you solve it, and it will help you improve your problem solving skill.

After solving it, I kept looking for better solutions. I stumbled upon another programmer's solution. It is in python, and really neat. It is really interesting, but later I found out it was wrong.

class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        A=s+s[::-1]
        cont=[0]
        for i in range(1,len(A)):
            index=cont[i-1]
            while(index>0 and A[index]!=A[i]):
                index=cont[index-1]
            cont.append(index+(1 if A[index]==A[i] else 0))
        print cont[-1]
        return s[cont[-1]:][::-1]+s

I myself looked at the Solution and saw it's interesting idea. At first, the algorithm concatenates the string and its reversed version. Then the following steps are similar to the steps for building KMP-table (or failure function) using in KMP algorithm. Why does this procedure work?

If you know KMP text searching algorithm, you will know its "lookup table" and steps to build it. Right now, I just show one important use of the table: it can show you the longest prefix of a string s that is also suffix of s (but not s itself). For example, "abcdabc" has the longest prefix which is also a suffix: "abc" (not "abcdabc" since this is the entire string!!!). To make it fun, we call this prefix is "happy substring" of s. So the happy substring of "aaaaaaaaaa" (10 a's ) is "aaaaaaaaa" (9 a's).

Now we go back and see how finding happy sub string of s can help solve the shortest palindrome problem.

Suppose that q is the shortest string added to the front of s to make the string qs is a palindrome. We can see that obviously length(q) < length(s) since ss is also a palindrome. Since qs is a palindrome, qs must end with q, or s = p+q where p is a sub string of s. Easily we see that p is also a palindrome. Therefore, in order to have shortest qs, q needs to be shortest. In turn, p is the longest palindromic sub string of s.

We call s' and q' are the reversed strings of s and q respectively. We see that s = pq, s' = q'p since p is a palindrome. So ss' = pqq'p . Now we need to find the longest p. Eureka! This also means that p is a happy sub string of the string ss'. That's how the above algorithm works!!!

However, after some thought, the above algorithm has some loophole. p is not a happy sub string of ss'! In fact, p is the longest prefix that is also a suffix of ss', but the prefix and suffix must not overlap each other. So let's make it more fun, we call "extremely happy sub string" of a string s is the longest sub string of s that is a prefix and also a suffix and this prefix and suffix must not overlap. On the other word, the "extremely happy sub string" of s must have length less than or equal half length of s.

So it turns out the "happy sub string" of ss' is not always "extremely happy sub string" of ss'. We can easily construct an example: s = "aabba". ss'="aabbaabbaa". The happy sub string of "aabbaabbaa" is "aabbaa", while the extremely happy sub string of "aabbaabbaa" is "aa". Bang!

Hence, the correct solution should be as following, based on the observation that length(p) <= length(ss')/2.

class Solution:
    # @param {string} s
    # @return {string}
    def shortestPalindrome(self, s):
        A=s+s[::-1]
        cont=[0]
        for i in range(1,len(A)):
            index=cont[i-1]
            while(index>0):
                if(A[index]==A[i]):
                    if index < len(s):
                        break
                index=cont[index-1]
            cont.append(index+(1 if A[index]==A[i] else 0))
        print cont[-1]
        return s[cont[-1]:][::-1]+s 

Hooray! As you can see, algorithms are interesting!

The link to the article I wrote here

Answer 4

Just append the reverse of initial substrings of the string, from shortest to longest, to the string until you have a palindrome. e.g., for "acbab", try appending "a" which yields "acbaba", which is not a palindrome, then try appending "ac" reversed, yielding "acbabca" which is a palindrome.

Update: Note that you don't have to actually do the append. You know that the substring matches since you just reversed it. So all you have to do is check whether the remainder of the string is a palindrome, and if so append the reverse of the substring. Which is what Ptival wrote symbolically, so he should probably get the credit for the answer. Example: for "acbab", find the longest suffix that is a palindrome; that is "bab". Then append the remainder, "ac", in reverse: ac bab ca.

Answer 5

I was also asked the same question recently, and here is what I wrote for my interview:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int isPalin ( char *str ) {
    int i, len=strlen(str);
    for (i=0; i<len/2; ++i)
        if (str[i]!=str[len-i-1])
            break;
    return i==len/2;
}

int main(int argc, char *argv[]) {
    if (argc!=2)
        puts("Usage: small_palin <string>");
    else {
        char *str = argv[1];
        int i=0, j, len=strlen(str);
        while ( !isPalin(str+i) )
            ++i;
        char *palin = malloc(len+1+i);
        *(palin+len+1+i) = '\0';
        strcpy(palin,str);
        for (i=i-1, j=0; i>=0; --i, ++j)
            *(palin+len+j) = str[i];
        puts(palin);
    }
    return 0;
}

I feel that the program would have been more structured had I written an strrev() function and checked palindrome using strcmp(). This would enable me to reverse the starting characters of the source string and directly copy it using strcpy().

The reson why I went with this solution is that before this question I was asked to check for palindrome and I already had that isPalin() in paper. Kind of felt using existing code would be better !!

Answer 6

Python code, should be easy to convert to C:

for i in range(1, len(a)):
    if a[i:] == a[i:][::-1]:
        break
print a + a[0:i][::-1]

Answer 7

Shortest palindrome -

• Reverse iterate from last positon + 1 to beginning
• Push_back the elements

---

#include <iostream>
#include <string>
using namespace std ;

int main()
{
    string str = "abcd" ;
    string shortStr = str ;
    for( string::reverse_iterator it = str.rbegin()+1; it != str.rend() ; ++it )
    {
        shortStr.push_back(*it) ;   
    }
    cout << shortStr << "\n" ;
}

And longer palindrome can be any longer.

Ex: abcd
Longer Palindrome - abcddcba, abcdddcba, ...

Answer 8

Some pseudo code, to leave at least a bit of work on you:

def shortPalindrome(s):
  for i in range(len(s)):
    pal = s + reverse(s[0:i])
    if isPalindrome(pal):
      return pal
  error()

Answer 9

My guess for the logic:

Say you string is [a1...an] (list of characters a1 to an)

• Find the smallest i such that [ai...an] is a palindrome.
• The smallest palindrome is [a1 ... a(i-1)] ++ [ai ... an] ++ [a(i-1) ... a1]

where ++ denotes string concatenation.

Answer 10

if string is made of k chars, I think you should add to this string the reversed (k-1) chars...

Answer 11

From the examples you shown looks like the longest palindrome is the original string concatenated with its reverse, and the shortest is the original string concatenated with its reverse except for the first character. But I'm pretty sure you want something more complex. Perhaps you can give better examples?