Description: We have to find the longest possible substring of a string S which is a palindrome.

Example:
Input:

S: “a b k k b z y”

Output:

Longest palindrome substring: “bkkb”

Algorithm and Implementation:
We’ll solve this problem using Dynamic Programming.
We define:
ispal(m, n)=  {   1   , if the substring between indexes ‘m’ and ‘n’ is a palindrome
0,     otherwise
}
ispal(m,n)=  {1, if string[m]=string[n] and ispal(m+1,n-1)=1
0, otherwise
}
The longest possible palindrome substring would be when value of ‘n-m+1’ is maximum , where ispal(m,n)=1.

To solve the problem using dynamic programming, we create a matrix ispal(j,k) of size nXn where j:row no. and k: column no.

/*The following function finds the longest palidromic substring.*/
int longestPalidromeSubstring( char *str )
{
int n = strlen( str ); /*get length of input string*/

/*ispal[i][j] will be 1 if the substring str[i..j] is a palindrome.*/
int ispal[n][n];
memset( ispal, 0, sizeof( ispal) );
int max=1;/*stores maximum length*/

for( int i = 0; i < n; ++i )
ispal[i][i] = 1;/*all substrings of length 1 are palindromes*/
/*check for sub-string of length 2.*/

int start = 0;
for( int i = 0; i < n-1; ++i )
{
if( str[i] == str[i+1] )
{
ispal[i][i+1] = 1;
start = i;
max= 2;
}
}

/* Check for lengths greater than 2 where ‘k’ is the length of substring*/
for( int k = 3; k <= n; ++k )
{
for( int i = 0; i < n - k + 1 ; ++i )
{
int j = i + k - 1;/*’j’ is ending index of substring*/

/*now consider the substring str[i…j]*/
/*checking for sub-string from ith index to jth index only if str[i+1…j-1] is a palindrome*/
if( ispal[i+1][j-1] && str[i] == str[j] )
{
ispal[i][j] = 1;
if( k > max)
{
start = i;
max = k;
}
}
}
}
/*PRINT LONGEST PALINDROME SUBSTRING-> str[start….start+max-1] */
return max; /*return length of longest palindrome substring*/
}

Time Complexity:
O(n*n)
Go to top