The Interview Question Today#5(28-02-19)

Question: 

Find the length of the longest palindrome subsequence.

Example:

 Input string: qwertykeyppyeky

 Output String: ykeyppyeky

  Length is: 10

Solution:

Approach:

We maintain a int table[n][n] that is filled in bottom up manner. The value of table[i][j] is 1(true), if the substring is palindrome, otherwise 0(false). To calculate table[i][j], we first check the value of table[i+1][j-1], if the value is 1(true) and str[i] is same as str[j], then we make table[i][j] 1(true). Otherwise, the value of table[i][j] is made 0(false).

C program:

#include <stdio.h>

#include <string.h>

// A utility function to print a substring

void printSubStr( char str[], int low, int high )

{int i;

    for( i = low; i <= high; ++i )

        printf("%c", str[i]); }

// This function prints the longest palindrome substring of str[].

// It also returns the length of the longest palindrome

int longestPalSubstr( char str[] )

{

    int i,k,n = strlen( str ); // get length of input string

    // table[i][j] will be false(0) if substring str[i..j] is not palindrome.

    // Else table[i][j] will be true(1)

    int table[n][n];

    memset(table, 0, sizeof(table));

    // All substrings of length 1 are palindromes

    int maxLength = 1;

    for ( i = 0; i < n; ++i)

        table[i][i] =1;

    // check for sub-string of length 2.

    int start = 0;

    for (i = 0; i < n-1; ++i)

    {

        if (str[i] == str[i+1])

        {

            table[i][i+1] =1;

            start = i;

            maxLength = 2;

        }

    }

    // Check for lengths greater than 2. k is length of substring

    for ( k = 3; k <= n; ++k)

    {

        // Fix the starting index

        for ( i = 0; i < n-k+1 ; ++i)

        {

            // Get the ending index of substring from

            // starting index i and length k

            int j = i + k - 1;

            // checking for sub-string from ith index to

            // jth index if str[i+1] to str[j-1] is palindrome

            if (table[i+1][j-1] && str[i] == str[j])

            {

                table[i][j] =1;

                if (k > maxLength)

                {

                    start = i;

                    maxLength = k;

           }

            }      }    }

    printf("Longest palindrome substring is: ");

    printSubStr( str, start, start + maxLength - 1 );

    return maxLength;

}

int main()

{

    char str[100];

    printf("Enter the String\n");

    scanf("%s",str);

    printf("\nLength is: %d\n", longestPalSubstr( str ) );

    return 0;

}

Output:

Enter the String

Qwertykeyppyeky

Longest palindrome substring is: ykeyppyeky

Length is: 10