class Solution {
public:

    int recursion(const string &s, int left, int right) {
        if (left == right) {
            return 1;
        }
        else if (left > right) {
            return 0;
        }

        int count = 0;

        while (left < right && s[left] == s[right]) {
            left++;
            right--;

            count += 2;
        }

        if (left == right)
            return count + 1;

        int leftStep = recursion(s, left + 1, right);
        int rightStep = recursion(s, left, right - 1);

        return count + max(leftStep, rightStep);
    }

    int longestPalindromeSubseq(string s) {
        return recursion(s, 0, s.size() - 1);
    }
};