Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length()<2) return s;
        int n = s.length();
        char[] c = s.toCharArray();

        Boolean dp[][] =new Boolean[n][n];
        int left = 0, right = 0;
        for(int i = n-1;i>=0;i--){
            for(int j = i; j<n; j++){
                if (j-i < 3) { //base case 
                 dp[i][j] = (c[i] == c[j]); 
               } else {
                  dp[i][j] = (c[i] == c[j] && dp[i+1][j-1]);
               }
                 if (dp[i][j] && (right-left <= j-i)) {
				   left = i;
				   right = j;
			   }
            }
        }
        return s.substring(left,right+1);
    }
}

Success

Runtime: 74 ms, faster than 20.61% of Java online submissions for Longest Palindromic Substring.

Memory Usage: 49.6 MB, less than 6.45% of Java online submissions for Longest Palindromic Substring.