Minimum characters required to add to given string to make it palindrome

Last Updated on March 25, 2022 by Ria Pathak

Concepts Used

Strings, LPS array KPS Algorithm

Difficulty Level

Hard

Problem Statement (Simplified):

Find the minimum number of characters required to add to the given string to make it a palindrome.

See original problem statement here

Test Case

Input:
2
aab
abc

Output:
1
2

Explanation:
Case-1:
We can make string 'aab' a palindrome by adding 'b' in front of the string. Adding 'b' converts string to 'baab'. So the answer is 1.

Case-2:
We can make string 'abc' a palindrome by adding 'cb' in front of the string. Adding 'cb' converts string to 'cbabc'. So the answer is 2.

Solving Approach :

LPS Array: A LPS array (Longest Prefix that is suffix) is an array which provide length and index of prefix of string which is also suffix of array. For example, if string is "abcbdab", LPS array for this string would be [0,0,0,0,0,1,2] suggesting the values at index 5 and 6 are 1ˢᵗ and 2ⁿᵈ character of string respectively.

1) We use LPS array from KPS Algorithm to solve this problem.
2) We concatenate the reverse of the string with any random non-alphabetic character in last to the current string.
3) LPS array defines the largest prefix which is also suffix in the string.
4) Here we are only interested in the last value of this LPS array because it shows us the largest suffix of the reversed string that matches the prefix of the original string i.e these many characters already satisfy the palindrome property.
5) Finally the minimum number of characters needed to make the string a palindrome is the length of the input string minus last entry of our LPS array.

Example

• Lets assume the string be "codec", its reverse would be "cedoc", so we concatenate both strings using a random character in between creating a new string i.e. "codec@cedoc".
• LPS array for the above string will be [0,0,0,0,1,0,1,0,0,0,1] which means last character of above string is 1ˢᵗ
  character of array. By LPS we can see, first and last element of given string is matching. Hence we need to insert lengthOfString – lastIndexOfLPSArray elements in string to make it palindrome. Hence 5-1 i.e. 4 elements are required.

Solutions

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

int main(){

  int test;
  scanf("%d", &test);

  while(test--){

    char a[1000000];
    scanf("%s",a);

    int sizeOfString = strlen(a);

    //Concatenating reverse of string to string
    int n=sizeOfString;

    a[n] = '`';
    a[n+1] = '\0';

    n = strlen(a);

    for(int i=0; i<n-1; i++){
      a[i+n] = a[n-i-2];
    }

    a[(2*n) + 1] = '\0';
    int lps[strlen(a)];

    //Creating lps array for the concatenated string
    lps[0] = 0; 
    int i = 1, len=0; 
    while (i < strlen(a)) 
    { 
        if (a[i] == a[len]) 
        { 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else 
        { 
            if (len != 0) 
            { 
                len = lps[len-1]; 
            } 
            else
            { 
                lps[i] = 0; 
                i++; 
            } 
        } 
    }

    printf("%d\n",sizeOfString-lps[strlen(a)-1]);
  }

}

#include<bits/stdc++.h>
using namespace std;

int main(){

  int test;
  cin>>test;

  while(test--){

    string a;
    cin>>a;

    int sizeOfString = a.length();

    //Concatenating reverse of string to string
    string b = a;
    reverse(b.begin(), b.end());
    a += a +'@' + b;

    int lps[a.length()];

    //Creating lps array for the concatenated string
    lps[0] = 0; 
    int i = 1, len=0; 
    while (i < a.length()) 
    { 
        if (a[i] == a[len]) 
        { 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else 
        { 
            if (len != 0) 
            { 
                len = lps[len-1]; 
            } 
            else
            { 
                lps[i] = 0; 
                i++; 
            } 
        } 
    }

    cout<<sizeOfString-lps[a.length()-1]<<endl;
  }

}

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

      Scanner sc = new Scanner(System.in);
      int test = sc.nextInt();

      while(test!=0){

        String a = sc.next();

        int sizeOfString = a.length();

        //Concatenating reverse of string to string

        StringBuilder sb = new StringBuilder(a); 
        sb.reverse();

        a += '@';

        a += sb.toString();

        int lps[] = new int[a.length()];

        //Creating lps array for the concatenated string
        lps[0] = 0; 
        int i = 1, len=0; 
        while (i < a.length()) 
        { 
            if (a.charAt(i) == a.charAt(len)) 
            { 
                len++; 
                lps[i] = len; 
                i++; 
            } 
            else 
            { 
                if (len != 0) 
                { 
                    len = lps[len-1]; 
                } 
                else
                { 
                    lps[i] = 0; 
                    i++; 
                } 
            } 
        }

        System.out.println(sizeOfString-lps[a.length()-1]);

        test--;
      }
  }
}

[forminator_quiz id="873"]

This article tried to discuss Strings, LPS array KPS Algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Strings, LPS array KPS Algorithm you can check out MYCODE | Competitive Programming.