Count Different Palindromic Subsequences

Intuition

Let `dp[i][j]` be the number of distinct palindromic subsequences inside the substring `s[i..j]`. When the two endpoints differ, any palindrome lives either in `s[i+1..j]` or `s[i..j-1]`, but palindromes contained in the shared interior `s[i+1..j-1]` are counted twice, so we subtract that overlap. When the endpoints are equal, we can wrap every interior palindrome with the matching character and also add the two single-character and double-character palindromes, but only if no identical character already sits strictly inside; otherwise those wrapped forms would be duplicated. To handle that we locate the leftmost and rightmost occurrences of the endpoint character between `i` and `j`. Careful modular arithmetic (adding the modulus before taking the remainder) keeps every value non-negative after the subtractions.

Algorithm walkthrough

1. 1Initialize `dp[i][i] = 1` because a single character is one palindrome by itself.
2. 2Process substrings in increasing length so every `dp` value on the right-hand side is already known.
3. 3If `s[i] != s[j]`, set `dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]` to merge both sides and remove the doubly counted interior.
4. 4If `s[i] == s[j]`, scan inward for the nearest matching character on each side to determine how many copies of that character lie strictly between `i` and `j`.
5. 5With no interior copy add `2 * dp[i+1][j-1] + 2`, with exactly one add `2 * dp[i+1][j-1] + 1`, and with two or more use `2 * dp[i+1][j-1] - dp[low+1][high-1]` to cancel duplicates.
6. 6After each assignment, normalize with `(value % MOD + MOD) % MOD` and finally return `dp[0][n-1]`.

Implementation

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        MOD = 10 ** 9 + 7
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] != s[j]:
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
                else:
                    low, high = i + 1, j - 1
                    while low <= high and s[low] != s[i]:
                        low += 1
                    while low <= high and s[high] != s[i]:
                        high -= 1
                    if low > high:
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2
                    elif low == high:
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1
                    else:
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[low + 1][high - 1]
                dp[i][j] = (dp[i][j] + MOD) % MOD
        return dp[0][n - 1]