Find the longest palindrome of a String [Amazon,Microsoft]

Problem:

Find the length and/or string of the longest palindrome of a string.

The problem appeared as an Interview question in Amazon, Microsoft.

Solution:

One important property of a palindrome is if we remove the first and last characters of it , it would be another palindrome.

So A string S[a..b] will be a palindrome if and only if S[(a+1)…(b-1)] is a palindrome.

We can use DP to solve the problem.

• Keep a 2D array of ARRAY [String.SIZE]  [String.SIZE] for keeping the length of palindrome found from the string.
• Each char of the string is 1 length palindrome sub string. So ARRAY[i][i] = 1 , here i=0….String.SIZE
• Now find the length of possible palindrome for  2 char length strings starting from each index of the string S.
• similarly find palindrome for 3,4,…..char length string of the provided String S.

Problem Link

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

using namespace std;

int _max(int a,int b)
{
	if(a<=b)
	return b;
	return a;
}
int findPalindrome(string s,int M,int *st,int *ed)
{
	int arr[M][M];
	
	int j;
	int max_len=1;
	(*st)=0;
	(*ed)=0;
	
	for(int i=0;i<M;i++)
		for(int j=0;j<M;j++)
			arr[i][j]=0;
	for(int i=0;i<M;i++)
	{
		arr[i][i]=1;
	}
	
	for(int len=2;len<=M;len++)
	{
		for(int i=0;(i+len-1)<M;i++)
		{
			j=i+len-1;
			if(s[i]==s[j] && len==2)
			{
				arr[i][j]=2;
				if(max_len<arr[i][j])
				{
					max_len = arr[i][j];
					(*st)=i;
					(*ed)=j;
				}
				
			}
			if(s[i]==s[j] && len>2 && arr[i+1][j-1]!=0)
			{
				arr[i][j]=arr[i+1][j-1]+2;
				if(max_len<arr[i][j])
				{
					max_len = arr[i][j];
					(*st)=i;
					(*ed)=j;
				}
				//cout<<s[i]<<s[j]<<" "<<i<<","<<j<<"\n";
			}
			/*if(s[i]!=s[j])
			{
				arr[i][j]=_max(arr[i+1][j],arr[i][j-1]);
			}*/
		}
	}
	return max_len;//arr[0][M-1];
}

int main() 
{
	int t,n,M;
	string s;
	scanf("%d",&t);
	while(t--)
	{
		cin>>s;
		M=s.size();
		int st,ed;
		//cout<<
		int length = findPalindrome(s,M,&st,&ed);//<<endl;
		//cout<<length<<"\n";
		for(int i=st;i<=ed;i++)cout<<s[i];cout<<endl;
	}
	return 0;
}