HackerHeap

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"

Solution 1:

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