Count All Palindromic Subsequence in a given String

The problem, simply

You get a word s. A subsequence is what you get by crossing out some letters and keeping the rest in the same order. A palindrome reads the same both ways, like bcb.

Count all the non-empty subsequences that are palindromes. Picks at different positions count as different, even if they spell the same thing: in aab, the first a and the second a are two separate picks. The count can be huge, so judges usually want it modulo 10^9 + 7.

A story to remember it

Picture it

Examples

Way 1: the simple way

Let count(i, j) be the answer for the letters from i to j.

1. One letter (i == j): 1.
2. Ends match (s[i] == s[j]): count(i+1, j) + count(i, j-1) + 1.
3. Ends differ: count(i+1, j) + count(i, j-1) - count(i+1, j-1).

Why the minus? Picks that skip both ends are inside both of the first two counts, so they were added twice. Why no minus when the ends match? Those middle picks were added twice, but each of them can also be wrapped in the two matching end letters to make a new palindrome. The extra copy pays for those. The + 1 is the pair of end letters alone.

(Listing all 2^n picks and checking each one also works, but it is O(2^n * n) and much slower to write.)

class Solution {
    long count(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 count(s, i + 1, j) + count(s, i, j - 1) + 1;
        }
        return count(s, i + 1, j) + count(s, i, j - 1) - count(s, i + 1, j - 1);
    }

    public long countPS(String s) {
        return count(s, 0, s.length() - 1);
    }
}

How long it takes: each call makes up to three calls on pieces only one or two letters shorter, so it grows exponentially, below O(3^n). Extra room: the chain of waiting calls, O(n).

Way 2: the clever way

There are only about n * n / 2 pieces. Keep dp[i][j] for each one, and fill the table by piece length: all length 1, then all length 2, and so on. Every box only reads boxes for shorter pieces, which are already filled.

1. dp[i][i] = 1 for every letter.
2. For each length from 2 to n, for each start i (end j = i + len - 1), use the rule from Way 1.
3. The answer is dp[0][n-1].

class Solution {
    public long countPS(String s) {
        final long MOD = 1_000_000_007L;
        int n = s.length();
        long[][] dp = new long[n][n];            // dp[i][j]: picks inside s[i..j]
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                long inner = (i + 1 <= j - 1) ? dp[i + 1][j - 1] : 0;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] + 1) % MOD;
                } else {
                    // add MOD so the subtraction never goes below zero
                    dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - inner + MOD) % MOD;
                }
            }
        }
        return dp[0][n - 1];
    }
}

How long it takes: about n^2 / 2 boxes, each filled in one step, O(n^2). Extra room: the table, O(n^2).

Watch out for

• Fill by length, not by rows from the top. dp[i][j] needs dp[i+1][j], which is in the row below.
• For a piece of length 2 there is no middle. Treat it as 0 instead of reading dp[i+1][i].
• This counts picks by position. If the question wants different spellings only, it is a different and harder problem (see below).

What interviewers ask next

• Count only distinct palindromes (aab would give 3: a, b, aa)? That is LeetCode 730. When the ends match, look for the same letter inside to avoid counting the same spelling twice. Still O(n^2).
• Longest palindromic subsequence? Same table shape, but use max and + 2: if ends match, 2 + dp[i+1][j-1], else max(dp[i+1][j], dp[i][j-1]).
• Count palindromic substrings (no gaps allowed)? Grow outwards from each center, O(n^2) time and O(1) room.
• Can you save memory? Yes. Loop i from n - 1 down to 0 and j upwards, and keep only two rows, for O(n) room.

Remember this

Grown-up words: crossing out letters gives a subsequence, a piece from i to j is an interval, adding two counts and taking away the overlap is inclusion and exclusion, and filling by length is interval DP.