# Longest Palindromic Substring

## Question

### Problem Statement

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

Example:

**Input:** "babad"

**Output:** "bab"

**Note:** "aba" is also a valid answer.


Example:

**Input:** "cbbd"

**Output:** "bb"


## 题解1 - 穷竭搜索

### 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 {
public String longestPalindrome(String s) {
if (s == null || s.isEmpty()) return "";

final int sLen = s.length();
int longest = 0, left = 0;
for (int i = 0; i < sLen; i++) {
for (int j = i; j < sLen; j++) {
if (j - i + 1 > longest && isPalindrome(s, i, j)) {
longest = j - i + 1;
left = i;
}
}
}

return s.substring(left, left + longest);
}

private boolean isPalindrome(String s, int left, int right) {
for (int i = left, j = right; i <= j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) return false;
}
return true;
}
}


## 题解2

### C++

string palindrome(string& s, int l, int r) {
while (l>=0 && r<s.size() && s[l]==s[r]) l--, r++;
return s.substr(l+1, r-l-1);
}

string longestPalindrome(string s) {
if (s.empty()) return s;

string res;
for (int i=0; i<s.size(); i++) {
string t;
t = palindrome(s, i, i);
if (t.size() > res.size()) res = t;

t = palindrome(s, i, i+1);
if (t.size() > res.size()) res = t;
}
return res;
}


### Java

public class Solution {
public String longestPalindrome(String s) {
if (s == null || s.isEmpty()) return "";

final int sLen = s.length();
int longest = 0, left = 0;
for (int i = 0; i < sLen; i++) {
// odd
int leftIndex = leftPalindromeIndex(s, i, i);
int palindromeLen = 2 * (i - leftIndex) + 1;
if (palindromeLen > longest) {
left = leftIndex;
longest = palindromeLen;
}
// even
leftIndex = leftPalindromeIndex(s, i, i + 1);
palindromeLen = 2 * (i - leftIndex + 1);
if (palindromeLen > longest) {
left = leftIndex;
longest = palindromeLen;
}
}

return s.substring(left, left + longest);
}

private int leftPalindromeIndex(String s, int left, int right) {
for (; left >= 0 && right < s.length(); left--, right++) {
if (s.charAt(left) != s.charAt(right)) break;
}
return left + 1;
}
}