# 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)
{
while (head < tail)
{
if (s[head] != s[tail])
return false;
head++;
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())
{
if (s[head] != s[tail])
break;
head--;
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 head = 0; head < s.size(); ++head)
{
maxLen[head][0] = true;
maxLen[head][1] = true;
}
for (int len = 2; len <= s.size(); ++len)
{
for (int head = 0; head < s.size(); ++head)
{
int tail = head + len - 1;
if (tail >= s.size())
break;
maxLen[head][len] = (s[head] == s[tail]) ? maxLen[head+1][len-2] : false;
if (maxLen[head][len] && len > maxStr.size())
maxStr = s.substr(head, len);
}
}
return maxStr;
}
};