Question

Due to mutations there could be some insertion of deletion which makes some palindromes not palindromes any more. For example, GCCACCG is a palindrome. Due to deletion, this sequence might be changed to CCACCG (“G” was deleted).

QUESTION: design an algorithm which takes an input string and return a palindrome by inserting the smallest number of letters. You are allowed to insert characters at any position of the string. For example, AAT can be turned into palindrome TAAT by one insertion T, and GCT into GCTCG with two insertions CG. Also provide the time complexity analysis (e.g. big-O notation).

Answer 1

The code is in C

// A recursive program to find minimum
// number insertions needed to make a string
// palindrome
#include<bits/stdc++.h>
using namespace std;

// A utility function to find
// minimum of two numbers
int min(int a, int b)
{ return a < b ? a : b; }

// Recursive function to find
// minimum number of insertions
int findMinInsertions(char str[], int l, int h)
{
   // Base Cases
   if (l > h) return INT_MAX;
   if (l == h) return 0;
   if (l == h - 1) return (str[l] == str[h])? 0 : 1;

   // Check if the first and last characters are
   // same. On the basis of the comparison result,
   // decide which subrpoblem(s) to call
   return (str[l] == str[h])?
                   findMinInsertions(str, l + 1, h - 1):
                   (min(findMinInsertions(str, l, h - 1),
                   findMinInsertions(str, l + 1, h)) + 1);
}

// Driver code
int main()
{
   char str[] = "geeks";
   cout << findMinInsertions(str, 0, strlen(str) - 1);
   return 0;
}