# 【DSAA】Longest Palindromic Substring

### 题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

#### 怎么处理字符串长度奇偶情况

• 各字符间插入特殊字符。比如插入：#
• 从相邻两个字符开始比较。

### 我的解法

1. 原字符间插入特殊字符（#），处理长度为偶数情况；
2. 循环遍历每个字符算出其最大回文子串的长度；
3. 再剔除得到的回文子串中的特殊字符（#）；

Java 代码实现

```public String longestPalindrome(String s) {

if (s == null || s.length() <= 1) {
return s;
}

//插入 # 解决偶数对称字符
s = insertSpecialChar(s, '#');

final int length = s.length();
// 最大回文子串长度
int maxLen = 0;
int[] longestIndex = new int[2];
int i = 0, j = 0;
for (int index = 1; index < length; index++) {
i = index - 1;
j = index + 1;
while ((i >= 0 && j <= length - 1) && (s.charAt(i) == s.charAt(j))) {
i--;
j++;
}

if (maxLen < (j - i - 1)) {
maxLen = j - i - 1;
longestIndex[0] = i + 1;
longestIndex[1] = j;//substring 方法 endIndex 可以等于length 。取值范围是[startIndex, endIndex)
}

}
final String longestPalindromeStr = s.substring(longestIndex[0], longestIndex[1]);
return deleteSpecialChar(longestPalindromeStr, '#'));
}

// 插入特殊字符
private String insertSpecialChar(String s, char specialChar) {
StringBuilder sBuilder = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
sBuilder.append(specialChar + String.valueOf(s.charAt(i)));
}
sBuilder.append(specialChar);

return sBuilder.toString();
}

//剔除
private String deleteSpecialChar(String s, char specialChar) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (specialChar != s.charAt(i)) {
stringBuilder.append(String.valueOf(s.charAt(i)));
}
}
return stringBuilder.toString();
}```

### 官方推荐解法1

```public String longestPalindrome(String s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
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;
}```

### 官方推荐解法2

```public String longestPalindromeOfficialSn(String s) {
if (s == null || s.length() <= 1) {
return s;
}
//插入 # 解决偶数对称字符
final String temp = insertSpecialChar(s, '#');

final int length = temp.length();

int centerIndex = 0, rightIndex = 0;
final int[] p = new int[length];

for (int i = 0; i < length; i++) {
// iMirror 为 i 的对称点
int iMirror = 2 * centerIndex - i;
int pMirror = (iMirror < 0) ? 0 : p[iMirror];

p[i] = (rightIndex > i) ? Math.min(pMirror, rightIndex - i) : 0;

int L = i - 1 - p[i];
int R = i + 1 + p[i];
while (L >= 0 && R < length && temp.charAt(L) == temp.charAt(R)) {
p[i]++;
L = i - 1 - p[i];
R = i + 1 + p[i];
}

if (i + p[i] > rightIndex) {
// 右移已算出的回文子串
rightIndex = i + p[i];
centerIndex = i;
}
}

// 找出最大回文子串: 数组中最大的数
int maxLength = 0, index = 0;
for (int j = 0; j < length; j++) {
if (maxLength < p[j]) {
maxLength = p[j];
index = j;
}
}

String ret = temp.substring(index - maxLength, index + maxLength);
System.out.println( "index = "+index+" maxLength "+maxLength);
return s.substring((index - maxLength)/2, (index + maxLength)/2);
}```

```int iMirror = 2 * centerIndex - i;
p[i] = (rightIndex > i) ? Math.min(pMirror, rightIndex - i) : 0;```
1. 变量含义：i 和 iMirror 表示字符串中两个字符索引，centerIndex 是其对称点索引。p[i]表示以i索引的字符为中心的左右对称字符对数。rightIndex 则是以centerIndex点字符的最大回文子串的最右边索引位置。
2. 由于对称性，iMirror 为 i 的对称点不难得出 iMirror = centerIndex - (i - centerIndex)，即代码中的 int iMirror = 2 * centerIndex - i;
3. 当前点i + 对称点iMirror的p[iMirror] 如果小于rightIndex则可得出p[i] = p[iMirror]，看下面代码：
```if(i + p[iMirror] < rightIndex){
p[i] = p[iMirror];
}else{
p[iMirror] >= rightIndex - i;
//根据p[centerIndex]的回文子串对称性可知，p[i]>=rightIndex - i; 超过rightIndex为未知情况，所以去最小值p[i] = rightIndex - i;
}

// 所以就得出了下面这句代码。其中i>=rightIndex的情况未比较过的字符，所以默认赋值0
p[i] = (rightIndex > i) ? Math.min(pMirror, rightIndex - i) : 0;```