## # 5. 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.

Example 1:

``````Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
``````

Example 2:

``````Input: "cbbd"
Output: "bb"
``````

### # Solution

Approach 1: Longest Common Substring and then check the substring's indices.

Approach 2: Starting from both the head and tail of the array, we compare each pair of characters towards each other (Time Limit Exceeded).

Approach 3: Starting from the middle of the array, we compare each pair of characters towards the reversed directions.

Approach 4: Dynamic programming.

Approach 5: Manacher's Algorithm: http://articles.leetcode.com/longest-palindromic-substring-part-ii/

### # Code (Python)

Approach 4:

``````    def longestPalindrome(self, string):
# idea: DP. is_palindrome[i][j] -- string[i:j+1] is a palindrome
# O(N^2) time, O(N^2) space
if not string:
return ''
longest_substring = string[0]
is_palindrome = [[False for _ in range(len(string))] for _ in range(len(string))]
for span in range(len(string)):
for start in range(len(string)):
end = start + span
if end >= len(string):
break
if span == 0:
is_palindrome[start][end] = True
elif span == 1:
is_palindrome[start][end] = (string[start] == string[end])
else:
is_palindrome[start][end] = is_palindrome[start+1][end-1] if string[start] == string[end] else False
if is_palindrome[start][end] and end - start + 1 > len(longest_substring):
longest_substring = string[start:end+1]
return longest_substring
``````

Approach 5:

``````    def longestPalindrome(self, string):
# idea: for each char in string, expand outwards to search for the longest palindrome
# O(N^2) time, O(1) space
if not string:
return ''
longest_substring = string[0]
for i in range(len(string)):
longest = self._longest(string, i, i)
if len(longest) > len(longest_substring):
longest_substring = longest
if i < len(string) - 1:
longest = self._longest(string, i, i+1)
if len(longest) > len(longest_substring):
longest_substring = longest
return longest_substring

def _longest(self, string, start, end):
longest = string[start]
while 0 <= start <= end < len(string) and string[start] == string[end]:
longest = string[start:end+1]
start -= 1
end += 1
return longest
``````

### # Code (C++)

Approach 1:

``````// Longest Common Substring and then check the substring's indices.
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
string r = s; // The reverse of s.
for (int i = 0; i < n/2; ++i)
{
std::swap(r[i], r[n-i-1]);
}
// maxCommonSubstringSize[x][y] is the longest common
// substring size between s and r ending in s[x-1] and r[y-1].
int maxCommonSubstringSize[n+1][n+1];
for (int i = 0; i <= n; ++i)
{
maxCommonSubstringSize[0][i] = 0;
maxCommonSubstringSize[i][0] = 0;
}
string res = "";
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
maxCommonSubstringSize[i][j] = 0;
if (s[i-1] == r[j-1])
{
maxCommonSubstringSize[i][j] =
maxCommonSubstringSize[i-1][j-1] + 1;
}
if (maxCommonSubstringSize[i][j] > res.size() &&
maxCommonSubstringSize[i][j] + n == i + j)
// The second condition is for the case like "aacdefcaa".
// The correct components for comparison are
// s[x−a[x][y]]⋯s[x−1] and r[y−a[x][y]]⋯r[y−1], where
// (x−a[x][y])+(y−1) = (x−1)+(y−a[x][y]) = n−1, that is
// x+y = a[x][y]+n
{
res = s.substr(
(i - 1) - maxCommonSubstringSize[i][j] + 1,
maxCommonSubstringSize[i][j]);
}
}
}
return res;
}
};
``````
``````// Longest Common Substring and then check the substring's indices.
// Space optimization with a one-dementional array.
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
string r = s; // The reverse of s.
for (int i = 0; i < n/2; ++i)
{
std::swap(r[i], r[n-i-1]);
}
// maxCommonSubstringSize[x] is the longest common
// substring size between s and r ending in s[x-1] and r[y-1].
int maxCommonSubstringSize[n+1];
for (int i = 0; i <= n; ++i)
{
maxCommonSubstringSize[i] = 0;
}
string res = "";
for (int i = 1; i <= n; ++i)
{
for (int j = n; j >= 1; --j)
{
maxCommonSubstringSize[j] = 0;
if (s[i-1] == r[j-1])
{
maxCommonSubstringSize[j] =
maxCommonSubstringSize[j-1] + 1;
}
if (maxCommonSubstringSize[j] > res.size() &&
maxCommonSubstringSize[j] + n == i + j)
// The second condition is for the case like "aacdefcaa".
{
res = s.substr(
(i - 1) - maxCommonSubstringSize[j] + 1,
maxCommonSubstringSize[j]);
}
}
}
return res;
}
};
``````

Approach 2:

``````// Starting from both the head and tail of the array, we compare each pair of characters towards each other.
// Time Limit Exceeded.
class Solution {
private:
bool isPalindrome(string s, int head, int tail)
{
{
return false;
tail--;
}
return true;
}
public:
string longestPalindrome(string s) {
int n = s.size();
string maxStr = "";
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n; ++j)
{
if (isPalindrome(s, i, j) && (j-i+1) > maxStr.size())
maxStr = s.substr(i, j-i+1);
}
}
return maxStr;
}
};
``````

Approach 3:

``````// Starting from the middle of the array, we compare each pair of characters towards the reversed directions.
class Solution {
private:
int longestPalindromeSize(string s, int head, int tail)
{
while (head >= 0 && tail < s.size())
{
break;
tail++;
}
return (tail-1) - (head+1) + 1;
}
public:
string longestPalindrome(string s) {
string maxStr = "";
for (int i = 0; i < s.size(); ++i)
{
int len = longestPalindromeSize(s, i, i);
if (len > maxStr.size())
{
maxStr = s.substr(i-len/2, len);
}
len = longestPalindromeSize(s, i, i + 1);
if (len > maxStr.size())
{
maxStr = s.substr(i-len/2+1, len);
}
}
return maxStr;
}
};
``````

Approach 4:

``````// DP.
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() == 0) return s;
string maxStr = s.substr(0, 1);
bool maxLen[s.size()][s.size() + 1];
{
}
for (int len = 2; len <= s.size(); ++len)
{