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.
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.
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.
- Recursive approach
- 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.
- Start and end positions are the same in the string, then the result is 1. (Which is the character at either start or end).
- 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.
- 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 . 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.
A | B | A | A | C | D | A | A | B | A | D | |
A | 1 | 1 | 3 | 3 | 3 | 3 | 4 | 5 | 7 | 9 | 9 |
B | 0 | 1 | 1 | 2 | 2 | 2 | 3 | 5 | 7 | 7 | 7 |
A | 0 | 0 | 1 | 2 | 2 | 2 | 3 | 5 | 5 | 5 | 5 |
A | 0 | 0 | 0 | 1 | 1 | 1 | 3 | 3 | 3 | 4 | 5 |
C | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 5 |
D | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
A | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 2 | 3 | 3 |
A | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 3 | 3 |
B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
A | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
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 . 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!.