最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

class Solution {
  public static String longestPalindrome(String s) {
        if (null == s || s.length() < 2) {
            return s;
        }
        int start = 0, end = 0;
        int max = -1;
        for (int i = 0; i < s.length(); ++i) {
            for (int j = 0; j <= i; ++j) {
                if (i - j < 0 || i + j >= s.length() || s.charAt(i - j) != s.charAt(i + j)) {
                    if (2 * j - 1 > max) {
                        max = 2 * j - 1;
                        start = i - (j - 1);
                        end = i + j;
                    }
                    break;
                }
                if (s.charAt(i - j) == s.charAt(i + j)) {
                    if (2 * j + 1 > max) {
                        max = 2 * j + 1;
                        start = i - j;
                        end = i + j + 1;
                    }
                }
            }
        }
        for (int i = 0; i < s.length(); ++i) {
            for (int j = 0; j <= i; ++j) {
                if (i - j < 0 || i + 1 + j >= s.length() || s.charAt(i - j) != s.charAt(i + 1 + j)) {
                    if (2 * j > max) {
                        max = 2 * j;
                        start = i - (j - 1);
                        end = i + j + 1;
                    }
                    break;
                }
                if (s.charAt(i - j) == s.charAt(i + 1 + j)) {
                    if (2 * j + 2 > max) {
                        max = 2 * j + 2;
                        start = i - j;
                        end = i + j + 2;
                    }
                }
            }
        }
        return s.substring(start, end);
    }
}

时间复杂度是O(n*n)

代码肯定还能再优化，时间复杂度就不会了。