Longest Palindromic Subsequence

Posted: 7 Nov, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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:

  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
Try Problem