class Solution
{
    HashMap<String, Integer> map = new HashMap<String, Integer>();

    public int longestPalindromeSubseq(String s)
    {
        return compute(s, 0, s.length()-1);
    }

    public int compute(String s, int low, int high)
    {
        if(low>high)    return 0;
        if(low==high)   return 1;

        if(map.containsKey(s))
            return map.get(s);

        if(s.charAt(low)==s.charAt(high))
        {
            int ans = compute(s, low+1, high-1);
            map.put(s.substring(low+1, high), ans);
            return 2+ans;
        }
        else
        {
            int ans1 = compute(s, low, high-1);
            int ans2 = compute(s, low+1, high);

            map.put(s.substring(low, high-1), ans1);
            map.put(s.substring(low+1, high), ans2);

            return Math.max(ans1, ans2);
        }
    }
}