# Count Different Palindromic Subsequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-different-palindromic-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/count-different-palindromic-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
Given a string s, return _the number of different non-empty palindromic subsequences in_ `s`. Since the answer may be very large, return it **modulo** `109 + 7`.

A subsequence of a string is obtained by deleting zero or more characters from the string.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences `a1, a2, ...` and `b1, b2, ...` are different if there is some `i` for which `ai != bi`.

**Example 1:**

**Input:** s = "bccb"
**Output:** 6
**Explanation:** The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

**Example 2:**

**Input:** s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
**Output:** 104860361
**Explanation:** There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 109 + 7.

**Constraints:**

* `1 <= s.length <= 1000`
* `s[i]` is either `'a'`, `'b'`, `'c'`, or `'d'`.

# Approaches
## Brute-Force by Generating All Subsequences
This approach involves generating every possible non-empty subsequence of the given string `s`. For each generated subsequence, we check if it is a palindrome. To count only the unique palindromic subsequences, we store them in a hash set. The final answer is the size of this set.
**Time:** O(N * 2^N). There are `2^N` subsequences. For each, palindrome checking and set insertion take time proportional to its length (up to O(N)). · **Space:** O(N * 2^N). The recursion depth is O(N). The set can store up to `2^N` subsequences, each of average length O(N).
**Pros:** Simple to understand and conceptualize.
**Cons:** Extremely inefficient and will time out for the given constraints (N <= 1000).; High space complexity due to storing all unique palindromic subsequences and the recursion stack.; Not practical for problems requiring modulo arithmetic on a large result.
### Explanation
We can use a recursive helper function to generate all subsequences. The function would take the current index and the subsequence built so far. At each index `i`, we have two choices: either include the character `s[i]` in the current subsequence or not. This leads to `2^N` total subsequences. The base case for the recursion is when we have traversed the entire string. At this point, if the generated subsequence is non-empty, we check if it's a palindrome. A palindrome check for a string of length `k` can be done in `O(k)` time. A `HashSet<String>` is used to store the unique palindromic subsequences found. The final result is the size of the set. This method is too slow for the problem's constraints but serves as a conceptual starting point.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    Set<String> palindromes = new HashSet<>();
    String s;
    int n;

    // This method is for illustration and will Time Limit Exceed.
    public int countPalindromicSubsequences(String s) {
        this.s = s;
        this.n = s.length();
        generate(0, new StringBuilder());
        return palindromes.size();
    }

    private void generate(int index, StringBuilder current) {
        if (index == n) {
            if (current.length() > 0 && isPalindrome(current.toString())) {
                palindromes.add(current.toString());
            }
            return;
        }

        // Exclude s.charAt(index)
        generate(index + 1, current);

        // Include s.charAt(index)
        current.append(s.charAt(index));
        generate(index + 1, current);
        current.deleteCharAt(current.length() - 1); // backtrack
    }

    private boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Initialize an empty `HashSet<String>` called `palindromes`.
- Define a recursive function `generate(index, currentSubsequence)`.
- Base Case: If `index` reaches the end of the string:
  - If `currentSubsequence` is not empty and is a palindrome, add it to the `palindromes` set.
  - Return.
- Recursive Step:
  - Call `generate(index + 1, currentSubsequence)` (character at `index` is not included).
  - Call `generate(index + 1, currentSubsequence + s.charAt(index))` (character at `index` is included).
- Start the process by calling `generate(0, "")`.
- The answer is `palindromes.size()`. Note that this approach is not feasible for the given constraints and does not handle the modulo arithmetic.

## Dynamic Programming (Cubic Time)
This approach uses dynamic programming to solve the problem. We define `dp[i][j]` as the number of unique palindromic subsequences in the substring `s[i...j]`. We build up the solution for larger substrings from the solutions for smaller substrings. The state transition involves a linear scan, leading to a cubic time complexity.
**Time:** O(N^3). There are O(N^2) states `(i, j)`. Each state computation involves a linear scan of the substring `s[i...j]` for each of the 4 characters, taking O(N) time. · **Space:** O(N^2) for the memoization table and recursion stack.
**Pros:** Correctly solves the problem using a clear DP recurrence relation.; Significantly more efficient than the brute-force approach.
**Cons:** The O(N^3) complexity is too slow for N=1000 and will result in a Time Limit Exceeded error.
### Explanation
The core idea is to count palindromes by partitioning them based on their boundary characters ('a', 'b', 'c', 'd'). For a substring `s[i...j]`, we iterate through each character `c` in the alphabet. We find its first occurrence `l` and last occurrence `r` within `s[i...j]`. 
- If `c` does not exist, it contributes 0.
- If `c` appears once (`l == r`), it contributes 1 palindrome (`"c"`).
- If `c` appears multiple times (`l < r`), it contributes `2 + dp[l+1][r-1]` palindromes. These are: `"c"`, `"cc"`, and `"c" + p + "c"` for each unique palindrome `p` in `s[l+1...r-1]`.
The total `dp[i][j]` is the sum of contributions from all four characters. This partitioning ensures no double counting. A 2D array `memo[n][n]` stores results to avoid recomputing for the same subproblem. The bottleneck is the linear scan to find `l` and `r` in each subproblem, which takes `O(j-i)` time.

```java
import java.util.Arrays;

class Solution {
    int[][] memo;
    String s;
    int MOD = 1_000_000_007;

    public int countPalindromicSubsequences(String s) {
        int n = s.length();
        this.s = s;
        this.memo = new int[n][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dp(0, n - 1);
    }

    private int dp(int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (memo[i][j] != -1) return memo[i][j];

        long ans = 0;
        for (char c = 'a'; c <= 'd'; c++) {
            int l = -1, r = -1;
            // This linear scan is the O(N) part of the transition
            for (int k = i; k <= j; k++) {
                if (s.charAt(k) == c) {
                    if (l == -1) l = k;
                    r = k;
                }
            }

            if (l == -1) { // Character not in s[i..j]
                continue;
            } else if (l == r) { // Character appears once
                ans++;
            } else { // Character appears multiple times
                ans += 2 + dp(l + 1, r - 1);
            }
        }
        
        memo[i][j] = (int)(ans % MOD);
        return memo[i][j];
    }
}
```
### Algorithm
- Initialize a 2D array `memo[n][n]` for memoization.
- Define a recursive function `dp(i, j)` that returns the number of unique palindromic subsequences in `s[i...j]`.
- Base Cases:
  - If `i > j`, return 0.
  - If `i == j`, return 1.
- Memoization check: If `memo[i][j]` is already computed, return it.
- Initialize `ans = 0` (as a long to prevent overflow).
- For each character `c` from 'a' to 'd':
  - Linearly scan `s[i...j]` to find the first index `l` and last index `r` of `c`.
  - If `c` is not found, continue.
  - If `l == r`, add 1 to `ans`.
  - If `l < r`, add `2 + dp(l+1, r-1)` to `ans`.
- Store `ans % MOD` in `memo[i][j]` and return it.
- The final answer is `dp(0, n-1)`.

## Optimized Dynamic Programming (Quadratic Time)
This is an optimized version of the cubic DP approach. The bottleneck of searching for the first and last occurrences of a character in each subproblem is removed by precomputing this information. This optimization reduces the time complexity to be quadratic, which is efficient enough for the given constraints.
**Time:** O(N^2). There are O(N^2) states. Each state is computed in O(alphabet_size) time, which is constant. Precomputation takes O(N * alphabet_size). · **Space:** O(N^2). O(N^2) for the DP table and O(N * alphabet_size) for the precomputation arrays.
**Pros:** Efficient enough to solve the problem within the time limits.; Builds upon the standard DP solution with a clear optimization strategy.
**Cons:** Requires extra space for precomputation arrays.; The logic, while efficient, can be slightly more complex to grasp initially compared to the unoptimized DP.
### Explanation
The DP state `dp[i][j]` and the recurrence relation remain the same as the `O(N^3)` approach. The key optimization is to precompute the indices of the next and previous occurrences for each character. We use two 2D arrays, `next[i][c]` and `prev[i][c]`, which store the index of the next occurrence of character `c` at or after `i`, and the previous occurrence at or before `i`, respectively. These tables can be populated in `O(N * alphabet_size)` time. 

With this precomputation, finding the first occurrence `l` and last occurrence `r` of a character `c` in `s[i...j]` becomes an `O(1)` lookup: `l = next[i][c-'a']` and `r = prev[j][c-'a']`. This reduces the work for each DP state from `O(N)` to `O(alphabet_size)`, which is constant. The overall time complexity becomes `O(N^2 * alphabet_size)`, which is efficient enough to pass. The DP is implemented iteratively (bottom-up) to avoid recursion overhead and potential stack overflow issues for large `N`.

```java
class Solution {
    public int countPalindromicSubsequences(String s) {
        int n = s.length();
        int MOD = 1_000_000_007;
        int[][] dp = new int[n][n];

        int[][] next = new int[n][4];
        int[][] prev = new int[n][4];

        for (int c = 0; c < 4; c++) {
            int p = -1;
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) - 'a' == c) p = i;
                prev[i][c] = p;
            }
            p = n;
            for (int i = n - 1; i >= 0; i--) {
                if (s.charAt(i) - 'a' == c) p = i;
                next[i][c] = p;
            }
        }

        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (len == 1) {
                    dp[i][j] = 1;
                    continue;
                }
                
                long currentAns = 0;
                for (int c = 0; c < 4; c++) {
                    int l = next[i][c];
                    int r = prev[j][c];

                    if (l > r) { // Character not in s[i..j]
                        continue;
                    } else if (l == r) { // Character appears once
                        currentAns++;
                    } else { // Character appears multiple times
                        long innerCount = (l + 1 > r - 1) ? 0 : dp[l + 1][r - 1];
                        currentAns += 2 + innerCount;
                    }
                }
                dp[i][j] = (int)(currentAns % MOD);
            }
        }
        
        return dp[0][n-1];
    }
}
```
### Algorithm
- Precomputation:
  - Create `next[n][4]` and `prev[n][4]` arrays.
  - Fill `next[i][c]` with the index of the next occurrence of character `c` at or after index `i`.
  - Fill `prev[i][c]` with the index of the previous occurrence of character `c` at or before index `i`.
- Initialize a 2D DP table `dp[n][n]`.
- Iterate `len` from 1 to `n` (substring length).
- Iterate `i` from 0 to `n-len` (start of substring). Let `j = i + len - 1`.
- If `len == 1`, set `dp[i][j] = 1`.
- If `len > 1`:
  - Initialize `ans = 0`.
  - For each character `c` from 'a' to 'd':
    - Find `l = next[i][c-'a']` and `r = prev[j][c-'a']`.
    - If `l > r` (char not in `s[i...j]`), continue.
    - If `l == r`, add 1 to `ans`.
    - If `l < r`, add `2 + dp[l+1][r-1]` to `ans`.
  - Set `dp[i][j] = ans % MOD`.
- The final answer is `dp[0][n-1]`.

# Solutions
### Java

```java
class Solution {
private
  final int MOD = (int)1 e9 + 7;
public
  int countPalindromicSubsequences(String s) {
    int n = s.length();
    long[][][] dp = new long[n][n][4];
    for (int i = 0; i < n; ++i) {
      dp[i][i][s.charAt(i) - 'a'] = 1;
    }
    for (int l = 2; l <= n; ++l) {
      for (int i = 0; i + l <= n; ++i) {
        int j = i + l - 1;
        for (char c = 'a'; c <= 'd'; ++c) {
          int k = c - 'a';
          if (s.charAt(i) == c && s.charAt(j) == c) {
            dp[i][j][k] = 2 + dp[i + 1][j - 1][0] + dp[i + 1][j - 1][1] +
                          dp[i + 1][j - 1][2] + dp[i + 1][j - 1][3];
            dp[i][j][k] %= MOD;
          } else if (s.charAt(i) == c) {
            dp[i][j][k] = dp[i][j - 1][k];
          } else if (s.charAt(j) == c) {
            dp[i][j][k] = dp[i + 1][j][k];
          } else {
            dp[i][j][k] = dp[i + 1][j - 1][k];
          }
        }
      }
    }
    long ans = 0;
    for (int k = 0; k < 4; ++k) {
      ans += dp[0][n - 1][k];
    }
    return (int)(ans % MOD);
  }
}

```

### CPP

```cpp
using ll = long long ; class Solution { public: int countPalindromicSubsequences ( string s ) { int mod = 1e9 + 7 ; int n = s . size (); vector < vector < vector < ll >>> dp ( n , vector < vector < ll >> ( n , vector < ll > ( 4 ))); for ( int i = 0 ; i < n ; ++ i ) dp [ i ][ i ][ s [ i ] - 'a' ] = 1 ; for ( int l = 2 ; l <= n ; ++ l ) { for ( int i = 0 ; i + l <= n ; ++ i ) { int j = i + l - 1 ; for ( char c = 'a' ; c <= 'd' ; ++ c ) { int k = c - 'a' ; if ( s [ i ] == c && s [ j ] == c ) dp [ i ][ j ][ k ] = 2 + accumulate ( dp [ i + 1 ][ j - 1 ]. begin (), dp [ i + 1 ][ j - 1 ]. end (), 0ll ) % mod ; else if ( s [ i ] == c ) dp [ i ][ j ][ k ] = dp [ i ][ j - 1 ][ k ]; else if ( s [ j ] == c ) dp [ i ][ j ][ k ] = dp [ i + 1 ][ j ][ k ]; else dp [ i ][ j ][ k ] = dp [ i + 1 ][ j - 1 ][ k ]; } } } ll ans = accumulate ( dp [ 0 ][ n - 1 ]. begin (), dp [ 0 ][ n - 1 ]. end (), 0ll ); return ( int ) ( ans % mod ); } };
```

### Python

```python
class Solution:
    def countPalindromicSubsequences(self, s: str) -> int: mod = 10 ** 9 + 7 n = len(s) dp = [[[0] * 4 for _ in range(n)] for _ in range(n)] for i, c in enumerate(s): dp[i][i][ord(c) - ord('a')] = 1 for l in range(2, n + 1): for i in range(n - l + 1): j = i + l - 1 for c in 'abcd': k = ord(c) - ord('a') if s[i] == s[j] == c: dp[i][j][k] = 2 + sum(dp[i + 1][j - 1]) elif s[i] == c: dp[i][j][k] = dp[i][j - 1][k] elif s[j] == c: dp[i][j][k] = dp[i + 1][j][k] else: dp[i][j][k] = dp[i + 1][j - 1][k] return sum(dp[0][- 1]) % mod

```