Longest Palindromic Subsequence

The problem, simply

You get a word. You may cross out any letters, but you may not move the ones that stay. The letters that stay must read the same from left to right and from right to left, like "level" or "abba".

What is the most letters you can keep? A word that reads the same both ways is a palindrome, and letters kept in order with gaps allowed are a subsequence. So this is the longest palindromic subsequence.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write f(i, j) for the best answer on the letters from i to j.

1. If i > j, the piece is empty: 0. If i == j, one letter: 1.
2. If the end letters s[i] and s[j] match, keep both: 2 + f(i + 1, j - 1).
3. Otherwise drop one end: max(f(i + 1, j), f(i, j - 1)).

The two tries in step 3 overlap. Dropping the left end and then the right end lands on the same piece as dropping the right end first.

class Solution {
    public int longestPalinSubseq(String s) {
        return f(s, 0, s.length() - 1);
    }

    private int f(String s, int i, int j) {
        if (i > j) return 0;                 // empty piece
        if (i == j) return 1;                // one letter
        if (s.charAt(i) == s.charAt(j)) {
            return 2 + f(s, i + 1, j - 1);   // keep both ends
        }
        return Math.max(f(s, i + 1, j), f(s, i, j - 1)); // drop one end
    }
}

How long it takes: every mismatch splits into two calls, O(2^n) in the worst case. Extra room: the call chain is at most n deep, O(n).

Way 2: the clever way

There are only about n * n / 2 pieces (i to j). Put each answer in a table dp[i][j]. A piece only needs answers for shorter pieces inside it, so fill the table from short pieces to long ones.

1. Every single letter: dp[i][i] = 1.
2. For lengths 2, 3, and so on up to n, for every start i (with j = i + len - 1):
3. If s[i] == s[j], then dp[i][j] = dp[i + 1][j - 1] + 2.
4. Else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
5. The answer is dp[0][n - 1], the top right box.

In the table, the box one row down is "drop the left end", the box one column left is "drop the right end", and the box down and left is "the inside".

class Solution {
    public int longestPalinSubseq(String s) {
        int n = s.length();
        if (n == 0) return 0;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = 1;        // one letter

        for (int len = 2; len <= n; len++) {             // short pieces first
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;     // keep both ends
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // drop one end
                }
            }
        }
        return dp[0][n - 1];
    }
}

When len is 2 and the ends match, dp[i + 1][j - 1] is a box below the diagonal. Java fills it with 0, which is the right answer for an empty middle.

How long it takes: about n^2 / 2 boxes, one quick step each, O(n^2). Extra room: the table, O(n^2). Row i only needs row i + 1, so if you loop i from n - 1 down to 0 you can keep two rows, O(n).

Watch out for

• Subsequence, not substring. "agbcba" has the palindromic substring "bcb" of length 3, but the subsequence answer is 5.
• On a match it is + 2, except for a single letter, which is 1. The base case dp[i][i] = 1 handles that.
• Empty string: return 0 before reading dp[0][n - 1].

What interviewers ask next

• Another way to see it? Yes: it equals the longest common subsequence of the word and the word reversed.
• Fewest deletions to make a palindrome: n - LPS. Fewest insertions to make a palindrome is the same number.
• Print the palindrome itself: walk from dp[0][n - 1]. On a match take both ends and move inward; otherwise move toward the bigger neighbor.
• Count all palindromic subsequences: same table shape, but add counts instead of taking a max, and subtract the double counted middle part.
• Longest palindromic substring is a different problem. There the middle must be a full palindrome too, and expand around center solves it in O(n^2) time with O(1) room.

Remember this

Grown-up words: the mirror bracelet is a palindrome, keeping beads in order is a subsequence, the chart over (start, end) pairs is interval dynamic programming, and the repeated stretches are overlapping subproblems.