Longest Palindromic Substring

Desicription

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

Example:

1
2
3
4
5
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example:

1
2
3
Input: "cbbd"
Output: "bb"

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
string longestPalindrome(string s) {
s.insert(0, "$");
int maxn = 1;
int left = 0;
int right = 0;
for(int i = 0; s[i]; i++){
int left_tmp = i, right_tmp = i;
while(s[right_tmp+1] == s[i])
right_tmp++;
i = right_tmp;
while(s[left_tmp-1] == s[right_tmp+1])
left_tmp--, right_tmp++;
if(right_tmp - left_tmp + 1 > maxn)
maxn = right_tmp - left_tmp + 1, right = right_tmp, left = left_tmp;
}
if(!left && !right)
return s.substr(1,1);
return s.substr(left, right - left + 1);
}
};