Problem Description

Given a string s, return the longest palindromic substring in s.

Example 1

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2

Input: s = "cbbd"
Output: "bb"

Solution

The key observation is the fact that only if s[i+1][j-1] is a palindrome, the substring s[i][j] could potentially be a palindrome. After realizing this, either we can expand palindrome from the center. That is, choose a center in s and grow it by expanding the palindrome on the left and right by 1. Another idea is to use dynamic programming. To construct a DP, the core is to disassemble a big problem to a smaller problem. In other words, to build the iterates. Here, the iterate is the fact at the beginning. Next is to determine the degree of freedom, value and the meaning of an element in the DP, here is 2. Note here dp[i][j] could mean whether the substring s[i][j] is a palindrome or not, or construct a dp[i][i+j] meaning the substring s[i][i+j] is a palindrome or not, then j+1 is basically the length of the substring. The final step is to make sure the update rule: always be sure to use the updated elements in the dp matrix.

Java Code

Code 1: grow the palindrome

class Solution {
    public String longestPalindrome(String s) {
        String ret="";
        int len = s.length(), n = 2 * len - 1;
        for(int i=0; i<n; i++){
            String tmp = palindromeAt(i, s, len);
            if(tmp.length() > ret.length()) ret = tmp;
        } 
        return ret;
    }

    public String palindromeAt(int pos, String s, int len) {
        String ret="";
        int ind = pos/2, left=ind, right=ind+1;
        boolean ispal = true;
        if(pos%2 == 0) {
            ret = s.substring(ind, ind+1);
            left = ind-1;
        }
        while(left>=0 && right<len && ispal){
            if(s.charAt(left) == s.charAt(right)){
                ret = s.substring(left, left+1) + ret + s.substring(right, right+1);
            }else{
                ispal = false;
            }
            left --;
            right ++;
        }
        return ret;
    }
}

Code 2: DP

class Solution {
    public String longestPalindrome(String s) {
        String ret="";
        int len = s.length();
        int[][] dp =  new int[len][len];
        for(int i=len-1;i>=0;i--){
            for(int j=len-1;j>=i;j--){
                if(i == j) dp[i][j] = 1;
                else if(j==i+1 && s.charAt(j)==s.charAt(i)) dp[i][j]=1;
                else if(dp[i+1][j-1] == 1 && s.charAt(j)==s.charAt(i)) dp[i][j]=1;
                if(dp[i][j]==1 && j-i+1>ret.length()) ret = s.substring(i,j+1);
            }
        }
        return ret;
    }
}