The Longest Palindromic Substring problem is:
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.
To solve this problem, first investigate following examples:
abcdefedchz
: the longest palindrome iscdefedc
, the left and right parts are symmetric to letterf
.acbbcae
: the longest palindromeacbbca
, which is symmetric to the (virtual) postion betweenbb
.a
: the longest palindrome is the lettera
.
Based on above investigations, we could summarize the solution as:
- For every letter in the string, find the longest repetitive characters to current letter, record the
start
andend
position; - Minus
start
position by one and see ifs[start]
is still identical tos[end]
. - If yes, iteratively compare
s[start--]
ands[end--]
until they are not equal. - The possible longest palindrome for current letter is
end-start-1
.
Following is my C++ implementation. This algorithm could be enhanced by not checking every letters, however, the time complexity will still be \( O(N^2) \). A better method is Manacher’s Algorithm, which has \( O(N) \) time complexity.
class Solution {
public:
string longestPalindrome(string s) {
if(s.empty())
return "";
int pd_start=0; // the start position of the palindrome
int pd_len=0; // the length of the palindrome
for(int i=0;i<s.length();++i) {
int start=i;
int end=i;
while(end<s.length() && s[start]==s[end])
end++;
start--;
while(start>=0 && end<s.length() && s[start]==s[end]) {
start--;
end++;
}
if(pd_len<end-start-1) {
pd_len=end-start-1;
pd_start=start+1;
}
}
return s.substr(pd_start,pd_len);
}
};