CODEWITHSUNDEEP
algorithmdata-structures
discoverAnkit
discoverAnkit

Reputation: 1151

Minimum number of characters to be inserted at the end of a string to make it a palindrome

The question is like this--

We have to find the minimum number of characters to be inserted at the end of a string to make it a palindrome.

So, in my efforts to do this problem, I figured that this is equivalent to finding the largest palindromic substring which is also a suffix of the string.

I could do this in O(n^2) easily but I am looking for a O(n) solution which is probably possible using modified KMP. Somebody please help me figure out.

Upvotes: 7

Views: 2348

Answers (2)

Rajat Singhal
Rajat Singhal

Reputation: 1

A simple code to insert minimum number of characters and return them to make the given string a pallindrome

#include <bits/stdc++.h>
using namespace std;
bool isPalin(char *s,int x,int l)
{
    for(int i=x,j=l-1;i<j;i++,j--)
        if(s[i]!=s[j])
            return 0;
    return 1;
}
char * f(char *s)
{
    // if s is NULL return NULL
    if(!s)
        return NULL;
    int i,l,j;
    l=strlen(s);
    for(i=0;i<l;i++)
    {
        // check if string is pallindrome from [i...l-1]
        if(isPalin(s,i,l) == 1)
            break;
    }
    // if s is already a pallindrome return NULL
    if(i==0)
        return NULL;
    int k=0;
    // make a char*
    char *ans = new char[i+1];
    for(i-=1;i>=0;i--)
        ans[k++]=s[i];
    ans[k++]='\0';
    return ans;
}

int main() {
    char *a = "wxytabbat";
    cout<<f(a)<<"\n";
    return 0;
}

Upvotes: 0

IVlad
IVlad

Reputation: 43477

I have an approach that uses hashing posted as an answer here.

You can indeed also use KMP. You can compute the prefix function for the reversed string, and then iterate your initial string from left to right:

KMP computes a function prefix[i] = longest prefix of the string that is a suffix of string[1..i]

However, we want to know the longest suffix of our string that is a prefix of the reversed string. Why? If we have:

15232 => reverse = 23251

Then the longest suffix of the string that is a prefix of the reversed string is 232. This is a palindrome, and it lets us find what you're asking because a suffix of the string overlaps a prefix of the reversed string if the two are palindromes.

You have the cases:

prefix[i] = length - i => you can get a palindrome of 
            length 2*prefix[i] centered at i and i+1

prefix[i] = length - i + 1 => you can get a palindrome of
            length 2*prefix[i] - 1 centered at i

prefix[i] < length - i => you can't have a palindrome, ignore this position

So it suffices to compute the prefix function of the KMP algorithm.

Upvotes: 6

Related Questions