Given a string S, find the longest palindromic substring in S

.Assumptions

• There exists one unique longest palindromic substring.
• The input S is not null.

Examples

Input: "abbc"

Output: "bb"

Input: "abcbcbd"

Output: "bcbcb"

Solution: dp[i][j]: i到j的子串是否回文

dp[i][j] = true, if i + 2 >= j && s.charAt(i) == s.charAt(j)

dp[i][j] = dp[i + 1][j – 1] && s.charAt(i) == s.charAt(j) if长度大于3

  public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) {
      return s;
    }
    boolean[][] dp = new boolean[s.length()][s.length()];
    int max = 1, start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
      for (int j = 0; j <= i; j++) {
        dp[j][i] = s.charAt(j) == s.charAt(i) && (j + 2 >= i || dp[j + 1][i - 1]);
        if (dp[j][i] && i - j + 1 > max) {
          max = i - j + 1;
          start = j;
          end = i;
        }
      }
    }
    return s.substring(start, end + 1);
  }