Longest Palindromic Subsequence [MEDIUM]

Company: Amazon, Rivigo, Paypal, LinkedIn

Question:

Given a String, find the longest palindromic subsequence

Input:
The first line of input contains an integer T, denoting no of test cases. The only line of each test case consists of a string S(only lowercase)

Output:
Print the Maximum length possible for palindromic subsequence.

Constraints:
1<=T<=100
1<=|Length of String|<=1000
 

Examples:
Input:
2
bbabcbcab
abbaab
Output:
7
4

CODE:

import java.util.*;

import java.lang.*;

import java.io.*;

class Solution {

public static int max (int x, int y) { return (x > y)? x : y; }

      

    // Returns the length of the longest palindromic subsequence in seq

    public static int lps(String seq)

    {

       int n = seq.length();

       int i, j, cl;

       int L[][] = new int[n][n];  // Create a table to store results of subproblems

      

       // Strings of length 1 are palindrome of length 1

       for (i = 0; i < n; i++)

           L[i][i] = 1;

        for (cl=2; cl<=n; cl++)

        {

            for (i=0; i<n-cl+1; i++)

            {

                j = i+cl-1;

                if (seq.charAt(i) == seq.charAt(j) && cl == 2)

                   L[i][j] = 2;

                else if (seq.charAt(i) == seq.charAt(j))

                   L[i][j] = L[i+1][j-1] + 2;

                else

                   L[i][j] = max(L[i][j-1], L[i+1][j]);

            }

        }

              

        return L[0][n-1];

    }

          

    /* Driver program to test above functions */

    public static void main(String args[])

    {

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();

        for(int mi=0;mi<m;mi++){

        String seq = sc.next();

        System.out.println(lps(seq));

        }

    }

}

EXECUTION TIME:0.31s