How do I figure out the least number of characters to create a palindrome?

Question

Given a string, figure out how many characters minimum are needed to make the word a palindrome. Examples:

ABBA : 0 (already a palindrome)
ABB: 1
FAE: 2
FOO: 1

Answer 1

Algorithms only, since this is probably homework [Apologies to Raymond, it's an interview question rather than homework, as his edits/comments make clear. However, the algorithms and added pseudo-code are still valid for that purpose, and I've added some C code at the end].

You need to find the longest palindrome at the end of the string. An algorithm to see if a string is a palindrome can be created by simply running one pointer from the start of the string and one from the end, checking that the characters they refer to are identical, until they meet in the middle. Something like:

function isPalindrome(s):
    i1 = 0
    i2 = s.length() - 1
    while i2 > i1:
        if s.char_at(i1) not equal to s.char_at(i2):
            return false
        increment i1
        decrement i2
    return true

Try that with the full string. If that doesn't work, save the first character on a stack then see if the remaining characters form a palindrome. If that doesn't work, save the second character as well and check again from the third character onwards.

Eventually you'll end up with a series of saved characters and the remaining string which is a palindrome.

Best case is if the original string was a palindrome in which case the stack will be empty. Worst case is one character left (a one-character string is automatically a palindrome) and all the others on the stack.

The number of characters you need to add to the end of the original string is the number of characters on the stack.

To actually make the palindrome, pop the characters off the stack one-by-one and put them at the start and the end of the palindromic string.

Examples:

String      Palindrome  Stack  Notes
------      ----------  -----  -----
ABBA            Y       -      no characters needed.

String      Palindrome  Stack  Notes
------      ----------  -----  -----
ABB             N       -
BB              Y       A      one character needed.
ABBA            Y       -      start popping, finished.

String      Palindrome  Stack  Notes
------      ----------  -----  -----
FAE             N       -
AE              N       F
E               Y       AF     two characters needed.
AEA             Y       F      start popping.
FAEAF           Y       -      finished.

String      Palindrome  Stack  Notes
------      ----------  -----  -----
FOO             N       -
OO              Y       F      one character needed.
FOOF            Y       -      start popping, finished.

String      Palindrome  Stack  Notes
------      ----------  -----  -----
HAVANNA         N       -
AVANNA          N       H
VANNA           N       AH
ANNA            Y       VAH    three characters needed.
VANNAV          Y       AH     start popping.
AVANNAVA        Y       H
HAVANNAVAH      Y       -      finished.

 

String          Palindrome   Stack      Notes
------          ----------   --------   -----
deoxyribo           N        -
eoxyribo            N        d
oxyribo             N        ed
:                   :        :
bo                  N        iryxoed
o                   Y        biryxoed   eight chars needed.
bob                 Y        iryxoed    start popping.
ibobi               Y        ryxoed
:                   :        :
oxyribobiryxo       Y        ed
eoxyribobiryxoe     Y        d
deoxyribobiryxoed   Y        -          finished.

Converting this method to "code":

function evalString(s):
    stack = ""
    while not isPalindrome(s):
        stack = s.char_at(0) + stack
        s = s.substring(1)
    print "Need " + s.length() + " character(s) to make palindrome."
    while stack not equal to "":
        s = stack.char_at(0) + s + stack.char_at(0)
        stack = stack.substring(1)
    print "Palindrome is " + s + "."

For those less interested in pseudo-code, here's a test program in C which does the trick.

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

static char *chkMem (char *chkStr) {
    if (chkStr == NULL) {
        fprintf (stderr, "Out of memory.\n");
        exit (1);
    }
    return chkStr;
}

static char *makeStr (char *oldStr) {
    char *newStr = chkMem (malloc (strlen (oldStr) + 1));
    return strcpy (newStr, oldStr);
}

static char *stripFirst (char *oldStr) {
    char *newStr = chkMem (malloc (strlen (oldStr)));
    strcpy (newStr, &(oldStr[1]));
    free (oldStr);
    return newStr;
}

static char *addFront (char *oldStr, char addChr) {
    char *newStr = chkMem (malloc (strlen (oldStr) + 2));
    sprintf (newStr, "%c%s", addChr, oldStr);
    free (oldStr);
    return newStr;
}

 

static char *addBoth (char *oldStr, char addChr) {
    char *newStr = chkMem (malloc (strlen (oldStr) + 3));
    sprintf (newStr, "%c%s%c", addChr, oldStr, addChr);
    free (oldStr);
    return newStr;
}

static int isPalindrome (char *chkStr) {
    int i1 = 0;
    int i2 = strlen (chkStr) - 1;
    while (i2 > i1)
        if (chkStr[i1++] != chkStr[i2--])
            return 0;
    return 1;
}

 

static void evalString (char *chkStr) {
    char * stack = makeStr ("");
    char * word = makeStr (chkStr);

    while (!isPalindrome (word)) {
        printf ("%s: no, ", word);
        stack = addFront (stack, *word);
        word = stripFirst (word);
        printf ("stack <- %s, word <- %s\n", stack, word);
    }
    printf ("%s: yes, need %d character(s)\n", word, strlen (stack));

    printf ("----------------------------------------\n");
    printf ("Adjusting to make palindrome:\n");
    while (strlen (stack) > 0) {
        printf ("   %s, stack <- %s\n", word, stack);
    word = addBoth (word, *stack);
    stack = stripFirst (stack);
    }
    printf ("   %s\n", word);
    printf ("========================================\n");

    free (word);
    free (stack);
}

int main (int argc, char *argv[]) {
    int i;
    for (i = 1; i < argc; i++) evalString (argv[i]);
    return 0;
}

Running this with:

mkpalin abb abba fae foo deoxyribo

gives the output:

abb: no, stack <- a, word <- bb
bb: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
   bb, stack <- a
   abba
========================================

 

abba: yes, need 0 character(s)
----------------------------------------
Adjusting to make palindrome:
   abba
========================================

 

fae: no, stack <- f, word <- ae
ae: no, stack <- af, word <- e
e: yes, need 2 character(s)
----------------------------------------
Adjusting to make palindrome:
   e, stack <- af
   aea, stack <- f
   faeaf
========================================

 

foo: no, stack <- f, word <- oo
oo: yes, need 1 character(s)
----------------------------------------
Adjusting to make palindrome:
   oo, stack <- f
   foof
========================================

 

deoxyribo: no, stack <- d, word <- eoxyribo
eoxyribo: no, stack <- ed, word <- oxyribo
oxyribo: no, stack <- oed, word <- xyribo
xyribo: no, stack <- xoed, word <- yribo
yribo: no, stack <- yxoed, word <- ribo
ribo: no, stack <- ryxoed, word <- ibo
ibo: no, stack <- iryxoed, word <- bo
bo: no, stack <- biryxoed, word <- o
o: yes, need 8 character(s)
----------------------------------------
Adjusting to make palindrome:
   o, stack <- biryxoed
   bob, stack <- iryxoed
   ibobi, stack <- ryxoed
   ribobir, stack <- yxoed
   yribobiry, stack <- xoed
   xyribobiryx, stack <- oed
   oxyribobiryxo, stack <- ed
   eoxyribobiryxoe, stack <- d
   deoxyribobiryxoed
========================================

Answer 2

I saw this question in a competition once. I was stumped then.

But i think i've gotten this after discussing it with my friends. The thing is to find the minimum characters to insert into a string, you need to find the longest palindrome its centered around.

Take the string "accaz"

Imagine the string accaz is the palindrome acca with z inserted at the end. So we need to add another z at the start. Another string :"mykma"

Imagine this to be mym with two characters k and a inserted into it. So we need to two more characters to make it a palindrome. (the palindrome would be amkykma).

I've written a program in Java implementing this.

import java.util.*;
import java.io.*;
public class MinPalin{

//Function to check if a string is palindrome
public boolean isPaindrome(String s){
    int beg=0;
    int end=s.length()-1;

    while(beg<end){
        if(s.charAt(beg)!=s.charAt(end)){
            return false;

        }
        beg++;
        end--;
    }

    return true;

}

public int MinInsert(String s){
    int min=0;
    if(isPaindrome(s)){
        return min;
    }

    min++;

    while(true){
        ArrayList<String> temp=comboes(s,min);
        if(hasPalindrome(temp)){
            return min;
        }
        else
            min++;
    }

}

/*
 * Returns an arraylist of strings, in which n characters are removed
* 
*/

public ArrayList<String> comboes(String s,int n){

    ArrayList<String> results=new ArrayList<String>();


    if(n==1){

        for(int i=0;i<s.length();i++){
            String text="";
            for(int j=0;j<s.length();j++){
                if(i!=j){

                    text=text+""+s.charAt(j);
                }


            }
            results.add(text);

        }

    }
    else{
        ArrayList<String> temp=new ArrayList<String>();

        for(int i=0;i<s.length();i++){
            String tempString="";
            for(int j=0;j<s.length();j++){
                if(i!=j){
                    tempString=tempString+s.charAt(j);
                }
            }
            temp=comboes(tempString, n-1);

            for(int j=0;j<temp.size();j++){
                results.add(""+temp.get(j));
            }
        }
    }

    return results;


}

public boolean hasPalindrome(ArrayList<String> text){
    for(String temp:text){
        if(isPaindrome(temp)){
            return true;
        }
    }

    return false;
}

public static void main(String[] args)throws IOException
 {
     System.out.println("Enter the word :");
     MinPalin obj=new MinPalin();
     BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
     int n=obj.MinInsert(r.readLine());
     System.out.println("Characters needed : "+n);
    }
}

Hope this helps.