# Longest Palindromic Subsequence

Posted: 7 Nov, 2020
Difficulty: Hard

## PROBLEM STATEMENT

#### 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:

1. 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].
2. 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