LeetCode #5

# Description:

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

## Example:

``````Example:

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"
Output: "bb"
``````

# Idea:

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n – 1 such centers.

You might be asking why there are 2n – 1 but not n centers? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as “abba”) and its center are between the two ‘b’s.

Time: O(n2) runtime, O(1) space

# Code:

``````class Solution {
public:
string longestPalindrome(string s) {
int max_len=0;
int start, end;

for(int i=0; i<s.size(); ++i){
int len1=expandAroundCenter(s, i, i);
int len2=expandAroundCenter(s, i, i+1);

if(len1>max_len){
max_len=len1;
start = i - len1/2;
end = i + len1/2;
}
if(len2>max_len){
max_len=len2;
start = i - (len2/2 - 1);
end = i + 1 + (len2/2 - 1);
}
}
// string substr (size_t pos = 0, size_t len = npos) const;
return s.substr(start, end-start+1);
}

int expandAroundCenter(const string &s, int left, int right){
while(left>=0 && right<s.size()&&s[left]==s[right]){
left--;
right++;
}
return right-left-1;
}
};
``````