Question

$\textsf{\textbf{Question}}\\\textsf{\hspace{1em} Given a String, try to make it a palindrome by adding characters}\\\textsf{\hspace{1em} in front of it. Hence, find the shortest palindrome after performing}\\\textsf{\hspace{1em} this alteration.}\\\\\textsf{\textbf{Example}}\\\texttt{\hspace{.5em} \symbol{73}nput: \textsl{`abcd'}}\\\texttt{\hspace{.5em} \symbol{79}uput: \textsl{`dcbabcd'}}\\\\\textsf{\textbf{Language:} Any}$

Answer 1

Answer:

The solution can be achieved by removing characters from the beginning of the string one by one and checking if the string is palindrome or not.  

For Example, consider the above string, s = “abede”.  

We check if the string is palindrome or not.  

The result is false, then we remove the character from the beginning of string and now string becomes “bede”.

We check if the string is palindrome or not. The result is again false, then we remove the character from the beginning of string and now string becomes “ede”.

We check if the string is palindrome or not. The result is true, so the output becomes 2 which is the number of characters removed from the string.

Explanation:

// C program to find minimum number of appends

// needed to make a string Palindrome

#include<stdio.h>

#include<string.h>

#include<stdbool.h>

 

// Checking if the string is palindrome or not

bool isPalindrome(char *str)

{

   int len = strlen(str);

 

   // single character is always palindrome

   if (len == 1)

       return true;

 

   // pointing to first character

   char *ptr1 = str;

 

   // pointing to last character

   char *ptr2 = str+len-1;

 

   while (ptr2 > ptr1)

   {

       if (*ptr1 != *ptr2)

           return false;

       ptr1++;

       ptr2--;

   }

 

   return true;

}

 

// Recursive function to count number of appends

int noOfAppends(char s[])

{

   if (isPalindrome(s))

       return 0;

 

   // Removing first character of string by

   // incrementing base address pointer.

   s++;

 

   return 1 + noOfAppends(s);

}

 

// Driver program to test above functions

int main()

{

   char s[] = "abede";

   printf("%d\n", noOfAppends(s));

   return 0;

}