class Solution {
    public String longestPalindrome(String s) {
        /*  Q30 dp playlist , similiar to Q22 
            the last true cell will be the LPS with length gap +1 
            which can be found by substring(i , j+1)
        */
        //making 2d dp
        int n = s.length();
        String ans = "";
        boolean dp[][] = new boolean[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] = true;

                else if(gap == 1)
                    dp[i][j] = s.charAt(i)==s.charAt(j) ? true : false;
                    
                else{
                    if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1];

                    //else default value is already false
                }

                //storing the substring of the last true value
                if(dp[i][j] == true) 
                ans = s.substring(i,j+1);
            }
        }

        return ans;
    }
}