1. class Solution {
  2.     // idea: longest palindromic subsequence will be length of LCS
  3.  
  4.     public int longestPalindromeSubseq(String s) {
  5.         int n = s.length();
  6.  
  7.         // reverse the string and stroe it in new string
  8.         String s2 = new StringBuilder(s).reverse().toString();
  9.         int m = s2.length();
  10.  
  11.         // step-1 create a matrix
  12.         // t[i][j] = LCS of first i chars of s and first j chars of reversed string
  13.         int[][] t = new int[n+1][m+1];
  14.  
  15.         // step-2 initialise the matrix with base condition
  16.         for(int i=0; i<n+1; i++)
  17.         {
  18.             for(int j=0; j<m+1; j++)
  19.             {
  20.                 // string length is 0, NO LCS found
  21.                 if(i == 0 || j == 0)
  22.                     t[i][j] = 0;
  23.             }
  24.         }
  25.  
  26.         // step-3 iterative code to find length of LCS
  27.         for(int i=1; i<n+1; i++)
  28.         {
  29.             for(int j=1; j<m+1; j++)
  30.             {
  31.                 // characters match
  32.                 if(s.charAt(i-1) == s2.charAt(j-1))
  33.                     t[i][j] = 1 + t[i-1][j-1];
  34.  
  35.                 // characters do not match
  36.                 else
  37.                     t[i][j] = Math.max(t[i-1][j], t[i][j-1]);
  38.             }
  39.         }
  40.         // The bottom-right cell contains the length of LPS
  41.         int lcsLength = t[n][m];
  42.         return lcsLength;
  43.     }
  44. }