### [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, and there exists one unique longest palindromic substring.

### [Analysis]

I’ve started out with an attempt to solve this problem in O(n), turns out, that would be way too complicated to handle special cases…

Here is what I’ve tried: initialize a vector of int which stores the longest palindrome found ending at index i. That is, “abacaba” would give me [1,1,3,1,3,5,7], and I just need to scan through the whole array and get the max of the whole array. This seems to be a viable solution, because a sequence of char [start, end] is a palindrome, if and only if [start+1, end-1] is also one. However, considering the case where we have consecutive duplicated characters like “cccccc”, this can become much more complicated to handle.

A straightforward solution is to scan through the whole string, and try to develop a longest palindrome on its left side and right side. The key though, is to recognize that there are only two cases for each character, namely left and right side both starting from index i, or left = i-1 and right = i+1. The time complexity is , acceptable in our case given the assumption that the maximum length of S is 1000.

class Solution { string developFromCenter(const string &s, int left, int right) { while (left >= 0 && right < s.length() && s[left] == s[right]) { left--; right++; } return s.substr(left+1, right-left-1); } public: string longestPalindrome(string s) { string res; if (s.empty()) return res; for (int i=0; i<s.length(); ++i) { string s1 = developFromCenter(s, i, i); if (s1.length() > res.length()) res = s1; string s2 = developFromCenter(s, i, i+1); if (s2.length() > res.length()) res = s2; } return res; } };