# Longest Palindromic Substring

• tags: [palindrome]

## 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(n2) time is acceptable. Can you do it in O(n) time.


## 題解1 - 窮舉搜索(brute force)

### Python

class Solution:
# @param {string} s input string
# @return {string} the longest palindromic substring
def longestPalindrome(self, s):
if not s:
return ""

n = len(s)
longest, left, right = 0, 0, 0
for i in xrange(0, n):
for j in xrange(i + 1, n + 1):
substr = s[i:j]
if self.isPalindrome(substr) and len(substr) > longest:
longest = len(substr)
left, right = i, j
# construct longest substr
result = s[left:right]
return result

def isPalindrome(self, s):
if not s:
return False
# reverse compare
return s == s[::-1]


### C++

class Solution {
public:
/**
* @param s input string
* @return the longest palindromic substring
*/
string longestPalindrome(string& s) {
string result;
if (s.empty()) return s;

int n = s.size();
int longest = 0, left = 0, right = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
string substr = s.substr(i, j - i);
if (isPalindrome(substr) && substr.size() > longest) {
longest = j - i;
left = i;
right = j;
}
}
}

result = s.substr(left, right - left);
return result;
}

private:
bool isPalindrome(string &s) {
int n = s.size();
for (int i = 0; i < n; ++i) {
if (s[i] != s[n - i - 1]) return false;
}
return true;
}
};


### Java

public class Solution {
/**
* @param s input string
* @return the longest palindromic substring
*/
public String longestPalindrome(String s) {
String result = new String();
if (s == null || s.isEmpty()) return result;

int n = s.length();
int longest = 0, left = 0, right = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
String substr = s.substring(i, j);
if (isPalindrome(substr) && substr.length() > longest) {
longest = substr.length();
left = i;
right = j;
}
}
}

result = s.substring(left, right);
return result;
}

private boolean isPalindrome(String s) {
if (s == null || s.isEmpty()) return false;

int n = s.length();
for (int i = 0; i < n; i++) {
if (s.charAt(i) != s.charAt(n - i - 1)) return false;
}

return true;
}
}


## 題解2 - 動態規劃(dynamic programming)

P[i, j] = P[i+1, j-1] AND s[i] == s[j]

P[i, i] = true

P[i, i+1] = (s[i] == s[i+1])

string longestPalindrome(string s) {
int n = s.length();
int maxBegin = 0;
int maxLen = 1;
bool table[1000][1000] = {false};

for (int i = 0; i < n; i++) {
table[i][i] = true;
}

for (int i = 0; i < n-1; i++) {
if (s[i] == s[i+1]) {
table[i][i+1] = true;
maxBegin = i;
maxLen = 2;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n-len+1; i++) {
int j = i+len-1;
if (s[i] == s[j] && table[i+1][j-1]) {
table[i][j] = true;
maxBegin = i;
maxLen = len;
}
}
}
return s.substr(maxBegin, maxLen);
}