Leetcode005 Longest Palindromic Substring

Problem:

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”

Intuition:

首先我们可以很明显的发现回文串具有对称的特征。既然是对称的，我们在编程的时候就一定要利用这个特征来减少算法复杂度。

因为每个回文串都必须有一个中心，所以我们就可以以回文串中心来作为切入点，开始写循环。需要注意的是回文串有两种形式，第一种是奇数长度的回文串。它以当前回文串中的某个字符为中心。第二种是偶数长度的回文串，它的中心在当前回文串中的字符之间的空字符中。

接下来要做的就是每个中心点返回一个以它或它右边的空字符为中心的最长回文串的长度。这个功能要如何完成呢？

注意到这里满足第三题中提到的滑动窗口的使用条件（给予限制条件，求最大长度类问题），所以直接用滑动窗口完成子方法就可以完成本题。

Solution:

public String longestPalindromeSolution(String s) {
      if (s == null || s.length() < 1) return "";
      int start = 0, end = 0;
      for (int i = 0; i < s.length(); i++) {
          //这里要考虑两种情况，回文数可能是总长度为奇数或者偶数，那么如果是奇数的话它的中心就都是i，如果是偶数的话它的中心就是i+1
          int len1 = expandAroundCenter(s, i, i);
          int len2 = expandAroundCenter(s, i, i + 1);
          int len = Math.max(len1, len2);
          if (len > end - start) {
              start = i - (len - 1) / 2;
              end = i + len / 2;
          }
      }
      return s.substring(start, end + 1);
  }

  private int expandAroundCenter(String s, int left, int right) {
      int L = left, R = right;
      while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
          L--;
          R++;
      }
      return R - L + 1;
  }