Count All Palindromic Subsequence in a given String

The problem, simply

A subsequence is what you get when you cross out some letters of a string and keep the rest in order. From abcb you can get ab, acb, bb and so on.

Count how many subsequences are palindromes, meaning they read the same both ways. Picks that use different spots count separately, even if they spell the same word. So in aab, the two single as count as two. The answer can be huge, so it is usually asked modulo 10^9 + 7.

A story to remember it

Picture it

Examples

Way 1: the simple way

List every pick. A string of n letters has 2^n - 1 non-empty picks, because each letter is either in or out. Check each one.

1. For every number mask from 1 to 2^n - 1, keep letter k when bit k of mask is on.
2. Check if that pick is a palindrome with two fingers.
3. Count the ones that are.

class Solution {
    public long countPS(String s) {
        int n = s.length();
        long count = 0;
        for (int mask = 1; mask < (1 << n); mask++) {     // every pick
            StringBuilder pick = new StringBuilder();
            for (int k = 0; k < n; k++) {
                if ((mask & (1 << k)) != 0) pick.append(s.charAt(k));
            }
            if (isPal(pick)) count++;
        }
        return count;
    }

    private boolean isPal(StringBuilder t) {
        for (int l = 0, r = t.length() - 1; l < r; l++, r--) {
            if (t.charAt(l) != t.charAt(r)) return false;
        }
        return true;
    }
}

How long it takes: 2^n picks, each checked in O(n), so O(2^n * n). Extra room: one pick at a time, O(n).

Way 2: the clever way

Let count(i, j) be the number of palindromic picks that use only letters from spot i to spot j. One letter alone gives 1. For a longer stretch, look at its two end letters.

• If the ends differ, no palindrome can use both ends. Every palindrome skips the left end or skips the right end. Add both counts, then take away the ones that skip both ends, because they were counted twice: count(i, j) = count(i+1, j) + count(i, j-1) - count(i+1, j-1).
• If the ends match, do the same, but now each middle palindrome also gets a twin wrapped between the two end letters, and the two ends alone make one more. The twins exactly pay back what we would take away: count(i, j) = count(i+1, j) + count(i, j-1) + 1.

Fill the chart from short stretches to long ones. The answer is in the top right box.

class Solution {
    static final long MOD = 1_000_000_007L;

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

        for (int len = 2; len <= n; len++) {                  // short stretches 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] + dp[i][j - 1] + 1) % MOD;
                } else {
                    long middle = (len > 2) ? dp[i + 1][j - 1] : 0;
                    // add MOD before % so the answer never goes negative
                    dp[i][j] = ((dp[i + 1][j] + dp[i][j - 1] - middle) % MOD + MOD) % MOD;
                }
            }
        }
        return dp[0][n - 1];
    }
}

How long it takes: the chart has about n^2 / 2 boxes and each takes a constant number of steps, O(n^2). Extra room: the chart, O(n^2).

Watch out for

• Do not forget the + 1 in the matching case. It counts the pair of end letters alone, like bb.
• The chart must be filled by length, or from the bottom row up. Filling it row by row from the top reads boxes that are still empty.
• When the stretch has length 2, the middle is empty. Use 0 for it, not dp[i+1][i] from a random place.
• Counting distinct palindromes is a different, harder problem. Ask which one is wanted.

What interviewers ask next

• Count only distinct palindromic subsequences? For matching ends you must look for the same letter inside the stretch and subtract the ones that would repeat. That is LeetCode 730, still O(n^2) with care.
• Longest palindromic subsequence instead of the count? Same chart shape: matching ends give 2 + inner, otherwise the bigger of the two neighbors.
• Count palindromic substrings (no gaps allowed)? Grow outwards from each of the 2n - 1 middles and count while the ends match, O(n^2) time and O(1) room.
• Can you save room? Fill the chart from the bottom row up. Each row only needs the row below it, so two rows of length n are enough, O(n) room.

Remember this

Grown-up words: a pick of letters in order is a subsequence, the chart is a dynamic programming table, filling short stretches first is interval DP, adding two counts and removing the overlap is inclusion and exclusion, and 10^9 + 7 is the usual modulus.