New update is available. Click here to update.

Last Updated: 7 Nov, 2020

Hard

```
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.
```

```
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.
```

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

```
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.
```

Approaches

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

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.