5. Longest Palindromic Substring

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"

<SOLVE>

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() < 2)
            return s;
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
       
        int left = 0;
        int right = 0;
       
        for(int j=0; j<s.length(); j++){
            for(int i=0; i<j; i++){
                boolean isInnerWordPalindrome = isPalindrome[i+1][j-1] || j - i  <= 2;
                if(s.charAt(i) == s.charAt(j) && isInnerWordPalindrome){
                    isPalindrome[i][j] = true;
                   
                    if(j-i > right-left){
                        left = i;
                        right = j;
                    }
                }
            }
        }
        return s.substring(left, right+1);
    }
}