Given a string s, find the longest palindromic substring in s.

You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

如果事先知道子串长度，可以从左右往里判断字符是否相等，可本题无法事先得知子串长度。

于是将遇到的字符当作“最中间”向外扩展成了比较合理的选项。开始考虑的是分为奇偶回文，如例子中的两种情况。后来看到一种更简洁的方法，每次把所有和最中间字符相同的字符都略去，等于看成“最中间”所有相等的字符（如果有）看作一体，这样就省去来判断奇偶的步骤。另外注意到，如果剩余的字符串长度不超过当前最长回文长度的一半，就可以提前跳出循环了。

另外，字符串类的题，还是用 C++ 的 string 写的方便，以后的算法题打算用C语言 + C++ string 来写，省去一些低级的字符处理。