# Longest Palindromic Substring

`Dynamic Programming`, `String`
Medium

## Question

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
Example
Given the string = `"abcdzdcab"`, return `"cdzdc"`.
Challenge
O(n^2) time is acceptable. Can you do it in O(n) time.
Tags
String
Related Problems
Easy Valid Palindrome 22 % Medium Longest Palindromic Substring 26 % Medium Palindrome Partitioning II 22 %

## Analysis

### 区间类动态规划

Time O(n^2), Space O(n^2)
`dp[i][j]`来存DP的状态，需要较多的额外空间: Space O(n^2)
DP的4个要素
• 状态：
• `dp[i][j]`: `s.charAt(i)``s.charAt(j)`是否构成一个Palindrome
• 转移方程
• `dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])`
• 初始化：
• `dp[i][j] = true` when `j - i <= 2`
• 结果：
• `maxLen = j - i + 1;`，并得到相应longest substring： `longest = s.substring(i, j + 1);`

## Solution

public class Solution {
/**
* @param s input string
* @return the longest palindromic substring
*/
public String longestPalindrome(String s) {
if(s == null || s.length() <= 1) {
return s;
}
int len = s.length();
int maxLen = 1;
boolean [][] dp = new boolean[len][len];
String longest = null;
for(int k = 0; k < s.length(); k++){
for(int i = 0; i < len - k; i++){
int j = i + k;
if(s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])){
dp[i][j] = true;
if(j - i + 1 > maxLen){
maxLen = j - i + 1;
longest = s.substring(i, j + 1);
}
}
}
}
return longest;
}
}

#### DP - Time O(n^2), Space O(n^2)

class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
String longestPStr = "";
int strLen = s.length();
boolean[][] dp = new boolean[strLen][strLen];
for (int len = 1; len <= strLen; len++) {
for (int i = 0; i < strLen; i++) {
int j = i + len - 1;
if (j >= strLen) {
break;
}
dp[i][j] = (len <= 2 || dp[i + 1][j - 1]) && s.charAt(i) == s.charAt(j);
if (dp[i][j] && len > longestPStr.length()) {
longestPStr = s.substring(i, j + 1);
}
}
}
return longestPStr;
}
}

#### *Another implementation DP - Time O(n^2), space O(n^2)

In the state transfer function: j - i < 2 could also be j - i <= 2
public String longestPalindrome(String s) {
int n = s.length();
String res = "";
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); //j - i 代表长度减去 1
if (dp[i][j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
}

#### Space Optimized DP - Time O(n^2), space O(n)

public String longestPalindrome7(String s) {
int n = s.length();
String res = "";
boolean[] P = new boolean[n];
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= i; j--) {
P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
if (P[j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
}

#### Expand Around Center - Time O(n^2) Space O(1)

public class Solution {
/**
* @param s input string
* @return the longest palindromic substring
*/
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
String longest = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
// get longest palindrome with center of i
String tmp = helper(s, i, i);
if (tmp.length() > longest.length()) {
longest = tmp;
}
// get longest palindrome with center of i, i+1
tmp = helper(s, i, i + 1);
if (tmp.length() > longest.length()) {
longest = tmp;
}
}
return longest;
}
// Given a center, either one letter or two letter,
// Find longest palindrome
public String helper(String s, int begin, int end) {
while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
begin--;
end++;
}
return s.substring(begin + 1, end);
}
}

#### Another expand-center implementation

class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
String longest = "";
for (int i = 0; i < s.length(); i++) {
// single center
String tmp = helper(s, i, i);
if (tmp.length() > longest.length()) {
longest = tmp;
}
// dual center
tmp = helper(s, i, i + 1);
if (tmp.length() > longest.length()) {
longest = tmp;
}
}
return longest;
}
// center expand helper function
// @return longest string centered at i, j
private String helper(String s, int i, int j) {
if (i >= s.length() || j >= s.length()) {
return "";
}
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
i--;
j++;
}
return s.substring(i + 1, j);
}
}

#### Expand Center - O(n^2) time, O(1) space

@jinwu
7 ms, faster than 99.69%
public class Solution {
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2)
return s;
for (int i = 0; i < len-1; i++) {
extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i+1); //assume even length.
}
return s.substring(lo, lo + maxLen);
}
private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}}