Longest Palindromic String

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:

Input: "babad"
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;
    }
};