LongestPalindromicSubsequence.java

/*
    Problem: Given a string, find the longest palindromic subsequence.

    Maintains right upper half of the table.
 */
public class LongestPalindromicSubsequence {
    // complexity: time O(n^2), space O(n^2)
    static int findLPS(String S) {
        int n = S.length();
        int[][] memo = new int[n][n];
        // a single char is a palindrome
        for (int i = 0; i < n; i++) {
            memo[i][i] = 1;
        }

        // fill the rest
        for (int k = 2; k <= n; k++) {
            for (int i = 0; i < n - k + 1; i++) {
                // ending index
                int j = i + k - 1;
                if (k == 2 && S.charAt(i) == S.charAt(j)) {
                    memo[i][j] = 2;
                } else if (S.charAt(i) == S.charAt(j)) {
                    memo[i][j] = memo[i + 1][j - 1] + 2;
                } else {
                    memo[i][j] = Math.max(memo[i][j - 1], memo[i + 1][j]);
                }
            }
        }
        return memo[0][n-1];
    }

    public static void main(String[] args) {
        String S = "AABCDEBAZ";
        System.out.println(findLPS(S));
    }
}

/*
References:
http://algorithms.tutorialhorizon.com/longest-palindromic-subsequence/
http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/
 */