☕ DSA Java Articles

Topics › Strings › Hard String Problems

Count Palindromic Subsequences

Medium TUF ID 231 A2Z

Java source ↗ Edit this article ↗

Problem

Given a string s of length n, count its non-empty subsequences that are palindromes. A subsequence is obtained by deleting zero or more characters without reordering the rest. Subsequences are identified by the positions they use, so two equal strings taken from different positions are counted separately. Return the count modulo 10^9 + 7.

Constraints: 1 ≤ n ≤ 1000 (the Java file also accepts the empty string and returns 0).

Example 1

s = "abcd"
answer = 4      // only the single letters a, b, c, d

Example 2

s = "aab"
answer = 4      // a (position 0), a (position 1), b, aa

Example 3

s = "abcb"
answer = 6      // a, b, c, b, bb, bcb

This is the “count all, not necessarily distinct” version. Counting only distinct palindromic subsequences is a different and harder problem.

Approach 1: Brute force

Intuition. Each position is either taken or skipped, so a string of length n has 2^n - 1 non-empty subsequences. Generate each one from a bit mask, test whether it reads the same backwards, and count. It is hopeless beyond about 20 characters, but it is the definition turned into code, which makes it the right reference for testing.

Algorithm.

  1. For every mask from 1 to 2^n - 1, build the subsequence of positions whose bits are set.
  2. If it equals its reverse, increment the count.
  3. Return the count modulo 10^9 + 7.
static int bruteForce(String s) {
    int n = s.length();
    if (n > 20) throw new IllegalArgumentException("brute force is for tiny inputs only");
    long count = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if ((mask >> i & 1) == 1) sb.append(s.charAt(i));
        }
        String t = sb.toString();
        if (t.equals(sb.reverse().toString())) count++;
    }
    return (int) (count % MOD);
}

Complexity. Time O(2^n · n). Space O(n) for the subsequence being built.

Building the recurrence

Let C(i, j) be the number of palindromic subsequences that use only positions i..j. Split them by whether they use the two end positions.

Adding the cases, the C(i+1, j-1) terms cancel when the ends match:

s[i] == s[j]:  C(i, j) = C(i+1, j) + C(i, j-1) + 1
s[i] != s[j]:  C(i, j) = C(i+1, j) + C(i, j-1) - C(i+1, j-1)
base cases:    C(i, i) = 1,   C(i, j) = 0 when i > j

The answer is C(0, n-1). There are only n^2 / 2 distinct (i, j) pairs, but plain recursion would revisit them exponentially often, which is why we store results.

Approach 2: Better, memoized recursion

Intuition. Implement the recurrence directly and cache each C(i, j) the first time it is computed. Values are stored already reduced modulo 10^9 + 7. The subtraction in the second case can then produce a negative number, so MOD is added before reducing.

Algorithm.

  1. Fill a memo table with -1.
  2. count(i, j): return 0 if i > j, 1 if i == j, the memo if present; otherwise apply the recurrence and store the result.
  3. Return count(0, n - 1).
static int memoized(String s) {
    int n = s.length();
    if (n == 0) return 0;
    int[][] memo = new int[n][n];
    for (int[] row : memo) Arrays.fill(row, -1);
    return count(s, 0, n - 1, memo);
}

static int count(String s, int i, int j, int[][] memo) {
    if (i > j) return 0;
    if (i == j) return 1;
    if (memo[i][j] != -1) return memo[i][j];
    long res;
    if (s.charAt(i) == s.charAt(j)) {
        res = (long) count(s, i + 1, j, memo) + count(s, i, j - 1, memo) + 1;
    } else {
        res = (long) count(s, i + 1, j, memo) + count(s, i, j - 1, memo)
                - count(s, i + 1, j - 1, memo) + MOD;   // + MOD keeps the value non-negative
    }
    return memo[i][j] = (int) (res % MOD);
}

Complexity. Time O(n^2): each pair is computed once with O(1) work. Space O(n^2) for the memo plus O(n) recursion depth, since every call shrinks the interval by one.

Approach 3: Optimal, bottom-up tabulation

Intuition. C(i, j) depends only on intervals that start later (i + 1) or end earlier (j - 1). So filling the table with i going down from n - 1 and, for each i, j going up from i + 1, guarantees that every needed value is ready. This removes the recursion and its stack, and it runs faster in practice.

Algorithm.

  1. For i = n - 1 down to 0: set dp[i][i] = 1.
  2. For j = i + 1 .. n - 1: apply the recurrence, treating dp[i+1][j-1] as 0 when the interval is empty.
  3. Return dp[0][n - 1].
static int tabulation(String s) {
    int n = s.length();
    if (n == 0) return 0;
    int[][] dp = new int[n][n];                    // dp[i][j] = answer for s[i..j]
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            long inner = (i + 1 <= j - 1) ? dp[i + 1][j - 1] : 0;
            long v;
            if (s.charAt(i) == s.charAt(j)) v = (long) dp[i + 1][j] + dp[i][j - 1] + 1;
            else v = (long) dp[i + 1][j] + dp[i][j - 1] - inner + MOD;
            dp[i][j] = (int) (v % MOD);
        }
    }
    return dp[0][n - 1];
}

Dry run on s = "abcb" (row i, column j):

        j=0  j=1  j=2  j=3
i=0      1    2    3    6
i=1           1    2    5
i=2                1    2
i=3                     1

Two cells in detail. dp[1][3] has equal ends b, b: dp[2][3] + dp[1][2] + 1 = 2 + 2 + 1 = 5, which is b, c, b, bb, bcb. dp[0][3] has ends a, b: dp[1][3] + dp[0][2] - dp[1][2] = 5 + 3 - 2 = 6.

Complexity. Time O(n^2), about 5 · 10^5 cell updates for n = 1000. Space O(n^2). Row i reads only row i + 1 and itself, so two one-dimensional arrays of length n would reduce the space to O(n) if memory were tight.

Edge cases and pitfalls