Longest palindromic subsequence length of a string

Given an input string of size ‘N’ characters. We aim to find maximum length subsequence which is palindromic. A subsequence string is a sequence that is formed by another sequence by removing zero or more characters. Whereas a palindrome string is a string that can be read the same from the backward as forward.

Here is the longest palindromic subsequence with length 9 is “ABAACAABA”.

We can solve this problem using the longest common subsequence length problem (LCS). To solve this using LCS, the first step we need to do is to reverse the input string. Once we reverse input string, now we have two strings one is the original string and the other one is reversed string. Finally, we have to take the longest common subsequence between these two strings which gives us the longest palindromic subsequence.

The result of LCS is palindromic.
int longestPalindromSubseq(int inp[], int len) {
    char *rev = reverse(inp, len);
    return longestCommonSubseqDP(inp, rev, len, len);
}

Though it solves our requirement, we have other direct approaches to solve this problem.

  1. Recursive approach
  2. Dynamic Programming

Recursion approach

The recursion formula for this problem is a simple 3 step process with a start and end positions in which one is the base case.

  1. Start and end positions are the same in the string, then the result is 1. (Which is the character at either start or end).
  2. If the character at the start position is the same as that at the end position then the result is 2 plus the longest palindrome subsequence of the next starting position to the previous end position.
  3. If both characters at start and end positions are not the same, then it is the maximum of longest palindrome subsequence of 1. start + 1 to end, 2. start to end-1 and 3. start+1 to end-1.

Formula is as sowing below.

F(A, L, S, E)  = 1 // if S = E
               = 2 + F(A, L, S+1, E-1)  // If A[S] = A[E]
               = maximum { F(A, L, S+1, E), F(A, L, S, E-1), F(A, L, S+1, E-1) } // For all other cases.

Where
A = Array of integers.
L = Length of input
S = Start position
E = End position

Let’s see the code for the recursion approach.

int longestPalindromSubseqRecur(char arr[], int len, int start, int end)
{
    if (start > end)
    {
        return 0;
    }
    if (start == end)
    {
        return 1;
    }
    if (arr[start] == arr[end])
    {
        return 2 + longestPalindromSubseqRecur(arr, len, start + 1, end - 1);
    }
    else
    {
        return max(
            longestPalindromSubseqRecur(arr, len, start + 1, end),
            longestPalindromSubseqRecur(arr, len, start, end - 1),
            longestPalindromSubseqRecur(arr, len, start + 1, end - 1));
    }
}

The complexity of this approach is exponential, which is O(3^N). To overcome this complexity problem we have a solution using dynamic programming.

Dynamic Programming Approach

To solve the problem in the dynamic programming approach, we use the same recursion formula. The formula for memorisation is as follows.

dp[i][j] = 1  // if i = j
         = 2 + dp[i+1][j-1]  // if A[i] = A[j]
         = maximum { dp[i+1][j], dp[i][j-1], dp[i+1][j-1] } // For all other cases.

Here
A is input array

We arrange the same input characters as both columns and rows as showing in below table.

ABAACDAABAD
A11333345799
B01122235777
A00122235555
A00011133345
C00001112235
D00000112235
A00000012233
A00000001133
B00000000111
A00000000011
D00000000001
Dynamic programming memorisation for string “ABAACDAABAD”.

Let’s see the code for this approach.

int longestPalindromSubseqDP(char inp[], int len)
{
    int dp[len][len];
    int i = 0, j = 0;
    int counter = 0;
    for (i = 0; i < len; i++)
    {
        for (j = 0; j < len; j++)
        {
            dp[i][j] = 0;
        }
    }
    i = j = 0;
    while (1)
    {
        if (counter == len)
        {
            break;
        }
        if (i == j)
        {
            dp[i][j] = 1;
        }
        else
        {
            if (inp[i] == inp[j])
            {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            }
            else
            {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1], dp[i + 1][j - 1]);
            }
        }
        i++;
        j++;
        if (j == len)
        {
            counter++;
            i = 0;
            j = counter;
        }
    }
    return dp[0][len - 1];
}

This approach gives us with a complexity of O(N*N). Where N is the length of the input string. For the length of the longest palindromic subsequence is the value at position DP[0][N-1].

Let’s see the complete code with main function in following gist.

// Output
Longest palindromic subsequence using Recursion: 9
Longest palindromic subsequence using Dynamic Programming: 9

These are two best examples of solving finding the length of longest palindromic subsequence of a given string problem. If you know any better approach than this, please let our readers know by commenting here below. Happy Learning!.

See more: