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:

  1. For every letter in the string, find the longest repetitive characters to current letter, record the start and end position;
  2. Minus start position by one and see if s[start] is still identical to s[end].
  3. If yes, iteratively compare s[start--] and s[end--] until they are not equal.
  4. 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);		
    }
};