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 is`cdefedc`

, the left and right parts are symmetric to letter`f`

.`acbbcae`

: the longest palindrome`acbbca`

, which is symmetric to the (virtual) postion between`bb`

.`a`

: the longest palindrome is the letter`a`

.

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`

and`end`

position; - Minus
`start`

position by one and see if`s[start]`

is still identical to`s[end]`

. - If yes, iteratively compare
`s[start--]`

and`s[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);
}
};
```