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