Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:

Input: “cbbd”
Output: “bb”

问题：
寻找字符串里面的最长回文子串。
啥叫回文串呢？
对于字符串s,如果它的转置s’ 等于s本身，那么字符串s就是回文串。
例如:s=1234,那么s’=4321,显然s不等于s’,于是s不是回文串。
s=abba，s’=abba，因为s==s’，于是s是个回文串。

解法：
对于一个字符串，遍历所有可能的回文串中心，从回文串中心往两边匹配。注意处理回文串长度为偶数的问题。当回文串的长度为偶数的时候，它的对称中心就不是整数了，例如s=eeee,s[1]与s[2]匹配。

时间复杂度：$O(n^2)$O(n2)

class Solution {
public:
	bool isValid(int length, int index)
	{
		return index >= 0 && index < length;
	}
	string longestPalindrome(string s) {
		int mid=0,l=s.length();
		size_t st=0, max = 1;
		for (mid = 0; mid < l; mid++)
		{
			int i;
			//奇数情况
			for (i = 1; i <l;)
			{
				if (isValid(l, mid + i) && isValid(l, mid - i) && s[mid + i] == s[mid - i])
				{
					i++;
				}
				else
				{
					break;
				}
			}
			i--;
			if ((i * 2 + 1) > max)
			{
				max = i * 2 + 1;
				st = mid - i;
			}
			//偶数情况
			for (i = 0; i < l;)
			{
				if (isValid(l, mid-i) && isValid(l, mid+i+1)&& s[mid-i] == s[mid +i+1])
				{
					i++;
				}
				else
				{
					break;
				}
			}
			i--;
			if (2 * (i + 1) > max)
			{
				max = (i+1) * 2;
				st = mid - i;
			}
		}
		return s.substr(st, max);
	}
};

结果：

Runtime: 20 ms, faster than 75.93% of C++ online submissions for Longest Palindromic Substring.
Memory Usage: 8.7 MB, less than 90.34% of C++ online submissions for Longest Palindromic Substring.