题意：
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. (Medium)
分析：
采用动态规划，dp[i][j]表示从s[i]到s[j]的字串是否回文，然后按照字串长度进行遍历，如果s[i] == s[j] && dp[i + 1][j - 1] == 1，则dp[i][j] = 1
并更新起始位置和最大长度。
初始化除了要将dp[i][i] i=0,1,2...n-1初始化外，还需要初始化dp[i][i+1]
最终得到维护好的最大字串起始位置和长度，返回该字串。
代码：
class Solution {
public:
string longestPalindrome(string s) {
int dp[][] = {};
int start = , length = ;
for (int i = ; i < s.size(); ++i) {
dp[i][i] = ;
}
for (int i = ; i < s.size() - ; ++i) {
if (s[i] == s[i + ]) {
dp[i][i + ] = ;
start = i;
length = ;
}
}
for (int k = ; k < s.size(); ++k) {
for (int i = ; i < s.size() - k; ++i) {
if (s[i] == s[i + k] && dp[i + ][i + k - ] == ) {
dp[i][i + k] = ;
start = i;
length = k + ;
}
}
}
return s.substr(start,length);
}
};
时间复杂度 O(n^2)， 空间复杂度 O(n^2)；
解法2：
考虑不采用dp数组，节省空间复杂度为O(1)；
对每个每个节点作为初始位置，利用helper函数，开始向外扩展，如果满足s[left] == s[right]， left--; right++继续判定；
直到不满足条件位置或边界，并更新最大长度和初始位置。
注意拓展节点时除了拓展单一节点情况，还需要拓展两个节点开始的情况 (与dp的初始化条件类似)；
代码：
class Solution {
private:
int helper(const string& s, int left, int right) {
int length = ;
while (left >= && right < s.size() && s[left] == s[right]) {
length = right - left + ;
left--;
right++;
}
return length;
}
public:
string longestPalindrome(string s) {
int start = , length = ;
for (int i = ; i < s.size() ; ++i) {
int l1 = helper(s, i, i);
if (l1 > length) {
length = l1;
start = i - (length / );
}
}
for (int i = ; i < s.size() - ; ++i) {
int l2 = helper(s, i, i+);
if (l2 > length) {
length = l2;
start = i - (length - ) / ;
}
}
return s.substr(start, length);
}
};