Given a stringS, find the longest palindromic substring inS. You may assume that the maximum length ofSis 1000, and there exists one unique longest palindromic substring.

Have you met this question in a real interview?

Yes

Example

Given the string ="abcdzdcab", return"cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

line 18 and line 22 not start = i, be careful of every line

class Solution {

public:

/\*\*

 \* @param s input string

 \* @return the longest palindromic substring

 \*/

string longestPalindrome\(string& s\) {

    // Write your code here

    if \(s.empty\(\)\){

        return "";

    }

    int start = 0, len = 1, len1 = 0, len2 = 0;

    for \(int i = 0; i < s.length\(\); ++i\) {

        len1 = expand\(s, i, i\);

        len2 = expand\(s, i, i + 1\);

        if \(len1 > len\) {

            len = len1;

            start = i - \(len - 1 >> 1\);

        }

        if \(len2 > len\) {

            len = len2;

            start = i - \(len - 2 >> 1\);

        }

    }



    return s.substr\(start, len\);

}

private:

int expand\(string& s, int i, int j\) {

    while \(i >= 0 && j <= s.length\(\) && s\[i\] == s\[j\]\) {

        --i;

        ++j;

    }

    return j - i - 1;

}

};