5. Longest Palindromic Substring

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"


最长回文子串

C++：

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         if (s.size() == 0)
 5             return "" ;
 6         int left = 0 , right = 0 ;
 7         for(int i = 0 ; i < s.size() ; i++){
 8             int len1 = expand(s,i,i) ;
 9             int len2 = expand(s,i,i+1) ;
10             int len = max(len1,len2) ;
11             if (len > right - left){
12                 left = i - (len-1)/2 ;
13                 right = i + len/2 ;
14             }
15         }
16         
17         return s.substr(left , right-left+1) ;
18     }
19     
20     int expand(string s , int L , int R){
21         while (L >= 0 && R < s.size() && s[L] == s[R]){
22             L-- ;
23             R++ ;
24         }
25         return R-L-1 ;
26     }
27 };