Longest Palindromic Subsequence

PROBLEM STATEMENT

You have been given a string ‘A’ consisting of lower case English letters. Your task is to find the length of the longest palindromic subsequence in ‘A’.

A subsequence is a sequence generated from a string after deleting some or no characters of the string without changing the order of the remaining string characters. (i.e. “ace” is a subsequence of “abcde” while “aec” is not).

A string is said to be palindrome if the reverse of the string is the same as the actual string. For example, “abba” is a palindrome, but “abbc” is not a palindrome.

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The only line of each test case contains a single string ‘A’ consisting of only lowercase English letters.

Output Format:

For each test case, print a single integer denoting the length of the longest palindromic subsequence in string ‘A’.

The output for each test case is in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10 ^ 2

Where ‘T’ is the number of test cases, and ‘N’ is the length of the string.

Time limit: 1 sec.

Approach 1

The main idea behind this approach is to use recursion. The idea is to compare the first character of the string A[i..j] with its last character. There are two possibilities:

If the first character of the string is the same as the last character, we include first and last characters in the palindrome and do a recursive call for the remaining substring A[i + 1, j - 1].
If the last character of the string is different from the first character, we return a maximum of the two values we get by
- removing the last character and doing a recursive call for the remaining substring A[i, j - 1].
- removing the first character and doing a recursive call for the remaining substring A[i + 1, j].

Let A[0..n-1] be the input string of length n and L(0, n-1) be the length of the longest palindromic subsequence of A[0..n-1].

If the first and last characters of A are the same, then L(0, n-1) = L(1, n-2) + 2.

Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

Following is a general recursive solution with all cases handled.

L(i, i) = 1 for all indexes i in the given string because every single character is a palindrome of length 1.
If the first and last characters are not same
- If (A[i] != A[j]) L(i, j) = max {L(i + 1, j), L(i, j - 1)}
If there are only 2 characters and both are same
- Else if (j == i + 1 && A[i] == A[j]) L(i, j) = 2
If there are more than two characters, and first and last characters are same
- Else L(i, j) = L(i + 1, j - 1) + 2

Try Problem

Approach 2

The LPS (Longest Palindromic Subsequence) has an optimal substructure and also exhibits overlapping subproblems. Let us consider a recursion tree for a sequence of length 6 having all distinct characters (say “abcdef”) whose LPS length is 1.

As we can see, the same sub-problems (highlighted in the same color) are getting computed again and again. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are memoized rather than being computed again and again. Like other typical Dynamic Programming (DP) problems, recomputations of the same subproblems can be avoided by constructing a temporary array DP[][] in a bottom-up manner.

In the bottom-up approach, we calculate the answer to small subproblems and then move to the bigger subproblems.

We will consider the state DP[i][j] to store the length of the longest palindromic subsequence of substring [i, j] of the given string.

First we store the answer to the base subproblem (DP[i][i] = 1). Next, we iterate over all possible lengths in increasing order, as we need to start from smaller subproblems and reach the bigger ones.

For the range [i, j]:

If both ends of the range match, the current answer (DP[i][j]) will be equal to the answer of the smaller range (DP[i+1][j-1]) plus 2.
Otherwise, if both ends don’t match, we check the answer of the smaller range that starts either from i or i + 1. After that, we store the maximum between both of these options.

Finally, the answer to the full problem is stored inside DP[0][n - 1], where ‘n’ is the length of the given string.

Try Problem