Minimum characters to be added at front to make string palindrome

Given a string str we need to tell minimum characters to be added at front of string to make

string palindrome.

Examples:

Input : str = "ABC"

Output : 2

We can make above string palindrome as "CBABC"

by adding "B" and "C" at front.

Input : str = "AACECAAAA"

Output : 2

We can make above string palindrome as "AAAACECAAAA"

by adding two "A" at front of string.

SOLUTION

                   We can solve this problem efficiently in O(n) time using lps array of KMP algorithm.

First we concat string by concatenating given string, a special character and reverse of given

string then we will get lps array for this concatenated string, recall that each index of lps array

represent longest proper prefix which is also suffix. We can use this lps array for solving the

problem.

                                          For string = AACECAAAA

                                         Concatenated String = AACECAAAA$AAAACECAA

                                          LPS array will be {0, 1, 0, 0, 0, 1, 2, 2, 2,

                                                                         0, 1, 2, 2, 2, 3, 4, 5, 6, 7}

    PROGRAM:

    public class Ma1 {

    public void pal1(String str){
        StringBuilder sb = new StringBuilder(str);
        String r = str+"$"+sb.reverse();
        int[] kmp = new int[r.length()];
        int i=1,l=0;kmp[0]=0;
        while(i < r.length()){
             if(r.charAt(i)==r.charAt(l)){
               l++;
               kmp[i]=l;
               i++;
             
           }
           else if(l != 0){
                   l = kmp[l-1];
                 
               }
           else{
                   kmp[i] =0;
                   i++;
               }
           }
       
         for( i = 0 ; i < kmp.length ; i++){
            System.out.print(kmp[i]);
        }
        int q = kmp[kmp.length-1];
        System.out.println(str.length()-q);
    }
   
    public static void main(String[] args) {
        Ma1 m = new Ma1();
        String s = "AACECAAAA";
        m.pal1(s);
    }
   

    }