CareerCup

Recursive: match up 2 "external" chars and go deeper:
Pseudocode:
string makePalin(string word){
if word[0] == word[n-1]{
return word[0] + makePalin(word[0:n-2]) + word[n-1]
} else{
return minLength(makePalin(word+word[0]), makePalin(word[n-1]+word))
}
}}}

also, quick question:
if I have f(char* str), how can I append chars to str inside the function?

public static string ConvertToPalindrome(string word, int n)
        {
            if (n < 1) return "";
            if (n == 1) return word;
            if (word[0] == word[n-1])
            {
                return word[0] + ConvertToPalindrome(word.Substring(1,n-2), n-2) + word[n-1];
            } else 
            {
                return word[0] + ConvertToPalindrome(word.Substring(1, n-1), n - 1) + word[0];
            }
        }

ConvertToPalindrome("abcba", 5); --> abcba
ConvertToPalindrome("yahoo", 5); --> yahoohay
ConvertToPalindrome("mahesh", 6); --> maheseham

just a question. Can we destroy the given string e.g. correct palindrome for mahesh would be 'maheseham' or 'mahsesham''or 'maheshseham' .

In first and second the word 'mahesh' is not maintained.
While in third palindorme 'mahesh' is maintained.

Also the problem statement says the minum number of letter to be added to make it a palindorme. It doesnt say that we can destroy the orginal string .

Correct me if i am wrong here ?

int b, e, i, j;
  gets (str);
  int len = strlen(str);
    if (len<=0) continue;
    b = 0; e = len-1;
    while (b < e) {
      while ( e < len && str[b]!=str[e] ) e++;
      if (e >= len) b++,e=len-1;
      else b++,e--;

      if (e<=b) {
        i=b; j=e;
        while (j<len&&str[i]==str[j]) i--,j++;
        if (j<len) e++;
      }
    }

    for (i=0;i<=b;i++)
      printf("%c",str[i]);
    for (i=e-1;i>=0;i--)
      printf("%c",str[i]);
    printf("\n");

So, if your input is "amanaplanacanal"
then it will print first "amanaplanac"
then "analpanama"
So, final result will be "amanaplanacanalpanama"

int run()
{
    ///const char * str = "yahoo";
    ///const char * str = "yoy";
    ///const char * str = "World";
    const char * str = "mahesh";
    int size = strlen(str);
    int m[size][size];
    memset(m, 0, sizeof(m));
    int len = 2;
    for(len = 2; len <= size; len ++) {
        for(int i = 0; i + len <= size; i ++) {
            int e = i + len - 1;
            int m1 = 1 + m[i][e-1];
            int m2 = (1 << 31) - 1;
            if(str[i] == str[e]) {
                if(i+1 <= e-1) m2 = m[i+1][e-1];
                else m2 = 0;
            }   
            int m3 = 1 + m[i+1][e];
            int mx = (m1 < m2) ? m1 : m2; 
            mx = (mx < m3) ? mx : m3; 
            m[i][i+len-1] = mx; 
        }   
    }   
    /*  
    for(int i = 0; i < size; i ++) {
        for(int j = 0; j < size; j ++) printf("%d ", m[i][j]);
        printf("\n");
    }
    */
    printf("%d \n", m[0][size-1]);
    return 0;
}

Let w be the word.
Given i, j(0<=i<j<n), you want to know the longest subsequence si of w[0,i] and subsequence sj of w[j,n-1], such that si == reverse(sj).
Using dp, you can compute the length of such subsequence efficiently.
By subsequence, I mean all characters in the subsequence appear in the same order as they are in w. A subsequence is not necessarily a substring.
Once you have the dp table T, you just need to find the largest number in T[i][i+1] or T[i][i+2], corresponding to palindromes with even or odd length respectively.
The total running time is O(n^2).

int FindNoOfWordsToBeAdded(char str[])
{
	int size =0;
	while(str[size])
		size ++;
		
	int i,j,p,q;
	int maxSubstringPalindromeSize = 0;
	int begin;
	int end;
	for(i=0;i<size;i++)
	{
		for(j=size-1; j>i;j--)
		{
			 p=i;
			 q=j;
			while((str[p]==str[q])&& p<q)
			{
				p++;
				q--;
			}

			if(p-q==1)
			{
				//this is a palindome
				//begins at i ends at j
				if(j-i+1 >maxSubstringPalindromeSize)
				{
					maxSubstringPalindromeSize = j-i+1;
					begin = i;
					end =j;
				}
			}
		}
	}

	if(maxSubstringPalindromeSize ==0)
		return size-1;

	//now in the left over word find out the unique characters
	int ctUniqueChars = size - maxSubstringPalindromeSize;
	
	//find no of unique characters in remaining 
	for(i=begin-1;i>=0;i--)
	{
		for(j=end+1;j<size;j++)
		{
			if(str[i]==str[j])
			{
				ctUniqueChars-=2;
				i--;
			}

		}
	}

	return ctUniqueChars;

}
int main()
{
	char str[] ="llagoogle";
	cout<<"\n No of words to convert into palindrome : "<< FindNoOfWordsToBeAdded(str);
	getchar();
}