Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is1000.

Have you met this question in a real interview?

Yes

Example

Given s ="bbbab"return4
One possible longest palindromic subsequence is"bbbb".

public class Solution {
    /**
     * @param s the maximum length of s is 1000
     * @return the longest palindromic subsequence's length
     */

    //last step: if the first item 0 and last item i - 1 both in the best solution, we need to know if 1, i - 2
    //           if the first item 0 is in but i - 1 is not then we need to know 0, i - 2
    //           if the first item 0 is not but i - 1 is in then we need to know 1, i - 1
    //sub-problem
    //set f[i][j] represents the length of longest palindrome sequence from ith item to jth item 
    //f[i][j] = Maht.max{f[i + 1][j], f[i][j - 1], f[i + 1][j - 1] + 2|S[i] == S[j]}
    public int longestPalindromeSubseq(String s) {
        // Write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] word = s.toCharArray();
        int n = word.length;
        int[][] f = new int[n][n];

        //init f[i][i] = 1
        int i, j, len;
        for (i = 0; i < n; i++) {
            f[i][i] = 1;
        }

        for (i = 0; i < n - 1; i++) {
            f[i][i + 1] = word[i] == word[i + 1] ? 2 : 1;
        }

        //start from len = 3
        for (len = 3; len <= n; len++) {
            for (i = 0; i <= n - len; i++) {
                j = i + len - 1;
                f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                if (word[i] == word[j]) {
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
                }
            }
        }

        return f[0][n - 1];

    }
}