class Solution { public int longestPalindromeSubseq(String s) { /* Q29 of dp series , gap1 strategy */ //making 2d dp array, S&m - every cell denotes LPS of that string int n = s.length(); int[][] dp = new int[n][n]; for(int gap = 0 ; gap < n ; gap++){ for(int i = 0 , j = gap; j < n ; i++ , j++){ if(gap == 0) dp[i][j] = 1; //for 1 character string LPS = 1 //for 2char string , LPS = 2 if c1=c2 else LPS = 1 else if(gap == 1) dp[i][j] = s.charAt(i)==s.charAt(j) ? 2 : 1; //i denotes prefix , j denotes suffix else{ //if c1 == c2 , LCS of middle part + 2 for both chars if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2; //else max of (prefix , suffix) else dp[i][j] = Math.max(dp[i][j-1] , dp[i+1][j]); } } } // for(int i = 0 ; i < n ; i++){ // for(int j = 0 ; j < n ;j++) // System.out.print(dp[i][j] + " "); // System.out.println(); // } return dp[0][n-1]; } }