5. Longest Palindromic Substring

• start, end index의 조합을 모두 시도하여 palindrome을 찾아보려고 했으나 실패함.

• 개별 index를 기준으로 양 옆으로 글자를 확장하면서 palindrome이 구성가능한지 알아본다.
• 단, 확장할 때 길이가 홀수, 짝수인 경우를 모두 고려해야 한다.
• 홀수인 경우는 현재 index를 기준으로 양옆으로 1개씩 확장하며 같은지 비교한다.
• 짝수인 경우는 현재 index와 바로 그 다음 index가 같은지 비교하고 그 다음부터 양옆으로 1개씩 확장하며 같은지 비교한다.

class Solution {
public:
    pair<int, int> expand(string& s, int start, int end) {
        while (start >= 0 && end < s.length() && s[start] == s[end]) {
            --start;
            ++end;
        }
        return {start + 1, end - 1};
    }

    string longestPalindrome(string s) {
        pair<int, int> result = {0, 0};
        for (int i = 0; i < s.length(); ++i) {
            // odd length
            auto cur = expand(s, i, i);
            if (cur.second - cur.first > result.second - result.first)
                result = cur;
            // even length
            if (i == s.length() - 1 || s[i] != s[i + 1]) continue;
            cur = expand(s, i, i + 1);
            if (cur.second - cur.first > result.second - result.first)
                result = cur;
        }
        return s.substr(
            result.first, 
            result.second - result.first + 1);
    }
};