005.md

5. Longest Palindromic Substring

Solution 1 (O(n^2))

class Solution {
public:
    string longestPalindrome(string s) {
        int left = 0, right = 0;
        int length = s.length(), max_length = 0;
        if (length == 0)
        	return "";
        for (int i = 0; i < length; i++) {
            // odd case
            for (int j = 0; j <= min(i, length - i - 1); j++) {
                if (s[i - j] != s[i + j])
                    break;
                if (j * 2 + 1 > max_length) {
                    left = i - j;
                    right = i + j;
                    max_length = j * 2 + 1;
                }
            }
            // even case
            if (i + 1 < length && s[i] == s[i + 1]) {
                for (int j = 0; j <= min(i, length - i - 2); j++) {
                    if (s[i - j] != s[i + j + 1])
                        break;
                    if (j * 2 + 2 > max_length) {
                        left = i - j;
                        right = i + j + 1;
                        max_length = j * 2 + 2;
                    }
                }
            }
        }
        return s.substr(left, max_length);
    }
};