Longest Palindromic Substring

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

Substring of string S:

S[i...j] where 0 <= i <= j < len(S)

Palindrome string:

A string which reads the same backwards. More formally, S is palindrome if reverse(S) = S.

Incase of conflict, return the substring which occurs first ( with the least starting index ).

Example :

```Input : "aaaabaaa"
Output : "aaabaaa"```
Method 1:

DP.

Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.

Stated more formally below:

Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.
Therefore,

P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )
The base cases are:

P[ i, i ] ← true
P[ i, i+1 ] ← ( Si = Si+1 )
This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…

Solution:

Time: O(n^2)
Space: O(n^2)

public class Solution {
public String longestPalindrome(String A) {
int n = A.length();
boolean[][] isP = new boolean[n][n];
for (int i = 0; i < n; i ++) {
isP[i][i] = true;
if (i + 1 < n && A.charAt(i) == A.charAt(i + 1)) {
isP[i][i + 1] = true;
}
}
// p[i][j] = true if p[i + 1][j - 1] && A[i] == A[j]
for (int j = 2; j < n; j ++) {
for (int i = 0; i < n; i ++) {
if ((i + j) < n && isP[i + 1][i + j - 1] && A.charAt(i) == A.charAt(i + j)) {
isP[i][i + j] = true;
}
}
}
int start = 0;
int end = 0;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (isP[i][j] && (j - i) > (end - start)) {
start = i;
end = j;
}
}
}
return A.substring(start, end + 1);
}
}

Method 2:

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2N-1 such centers.

You might be asking why there are 2N-1 but not N centers?

The reason is that the center of a palindrome can be in between two letters.

Such palindromes have even number of letters (such as “abba”) and their center are between the two ‘b’s.

Since expanding a palindrome around its center could take O(N) time, the overall complexity is O(N2).

Solution:

Time: O(n^2)
Space: O(1)

public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
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);
//根据 i 和 len 求得字符串的相应下标
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;
}

Method 3:

Solution:

Time: O(n)
Space: O(n)

public class Solution {
public String longestPalindrome(String A) {
String str = processed(A);
int[] p = new int[str.length()];
int C = 0, R = 0;
for (int i = 1; i < str.length() - 1; i ++) {
int iMirror = 2 * C - i;
if (i < R) {
p[i] = Math.min(R - i, p[iMirror]);
} else {
p[i] = 0;
}
// expand from R + 1, this won't do anything if p[i] == p[iMirror]
// this while loop will run at most n times because i + p[i] or R increases
// monotinically
while (str.charAt(i + p[i] + 1) == str.charAt(i - p[i] - 1)) {
p[i]++;
}
if (i + p[i] > R) {
C = i;
R = i + p[i];
}
}
int maxLen = 0;
for (int i = 0; i < p.length; i ++) {
if (p[i] > maxLen) {
maxLen = p[i];
C = i;
}
}
int start = (C - maxLen) / 2;
return A.substring(start, start + maxLen);
}

private String processed(String A) {
StringBuilder sb = new StringBuilder("^#");
for (int i = 0; i < A.length(); i ++) {
char c = A.charAt(i);
sb.append(c);
sb.append("#");
}
sb.append("\$");
return sb.toString();
}
}