Given a string s, count how many different non-empty palindromic subsequences exist in s. Since the answer may be very large, return it modulo 10^9 + 7.
1 <= s.length <= 1000; s consists only of lowercase English letters.
At first, it might seem natural to try generating all possible subsequences and checking which ones are palindromes. However, this brute-force method is impractical because the number of subsequences grows exponentially with the length of s. For example, a string of length 20 has over a million subsequences.
Instead, we need an efficient way to count all unique palindromic subsequences. Dynamic programming is a good fit for this problem because:
We use dynamic programming with a 2D table dp[i][j], where each entry represents the number of different palindromic subsequences in the substring s[i..j].
i, dp[i][i] = 1.
s[i] != s[j], then dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]. This counts palindromic subsequences ending at j, starting at i, and subtracts the overlap.s[i] == s[j], things get more interesting:
low be the first occurrence of s[i] after i, and high be the last occurrence of s[j] before j.s[i] between i and j, then: dp[i][j] = 2 * dp[i+1][j-1] + 2 (one for the single character, one for the pair).dp[i][j] = 2 * dp[i+1][j-1] + 1.dp[i][j] = 2 * dp[i+1][j-1] - dp[low+1][high-1] (subtract the overlapping palindromic subsequences counted twice).10^9 + 7 at every step.
dp[0][n-1] gives the number of distinct palindromic subsequences for the entire string.
We also use pre-processing to quickly find the next and previous occurrences of each character, which helps in efficiently determining low and high.
Let's use the input s = "bccb":
We fill the dp table diagonally, starting with substrings of length 1, then 2, and so on. At each step, we use the recurrence to count palindromic subsequences, ensuring we only count unique ones.
For i=0, j=3 ("bccb"), since s[0]==s[3] ("b"), we look for the next and previous occurrence of "b" between 0 and 3. The only other "b" is at 0 and 3, so there are no others between them. Thus, dp[0][3] = 2 * dp[1][2] + 2. dp[1][2] is for "cc", which is 2 (for "c" and "cc"). So dp[0][3] = 2*2 + 2 = 6.
The distinct palindromic subsequences are: "b", "c", "bb", "cc", "bcb", "bccb".
O(2^n) time and space, which is infeasible for n > 20.
n x n table, where n is the length of s, so time complexity is O(n^2).low and high can be done in O(1) with preprocessing, or O(n) otherwise.O(n^2) for the DP table.
This problem is a classic application of dynamic programming for counting unique palindromic subsequences. The key insight is to use a DP table to avoid redundant computation and to carefully handle overlapping cases using inclusion-exclusion principles. Efficient pre-processing for character positions helps achieve an optimal O(n^2) solution, making it feasible even for strings of length up to 1000.
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]) % MOD
else:
low = i + 1
high = j - 1
while low <= high and s[low] != s[i]:
low += 1
while low <= high and s[high] != s[j]:
high -= 1
if low > high:
dp[i][j] = (2 * dp[i+1][j-1] + 2) % MOD
elif low == high:
dp[i][j] = (2 * dp[i+1][j-1] + 1) % MOD
else:
dp[i][j] = (2 * dp[i+1][j-1] - dp[low+1][high-1]) % MOD
if dp[i][j] < 0:
dp[i][j] += MOD
return dp[0][n-1]
class Solution {
public:
int countPalindromicSubsequences(string s) {
const int MOD = 1000000007;
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (s[i] != s[j]) {
dp[i][j] = ((dp[i+1][j] + dp[i][j-1]) % MOD - dp[i+1][j-1]) % MOD;
} else {
int low = i + 1, high = j - 1;
while (low <= high && s[low] != s[i]) ++low;
while (low <= high && s[high] != s[j]) --high;
if (low > high) {
dp[i][j] = (2 * dp[i+1][j-1] + 2) % MOD;
} else if (low == high) {
dp[i][j] = (2 * dp[i+1][j-1] + 1) % MOD;
} else {
dp[i][j] = ((2 * dp[i+1][j-1]) % MOD - dp[low+1][high-1]) % MOD;
}
}
if (dp[i][j] < 0) dp[i][j] += MOD;
}
}
return dp[0][n-1];
}
};
class Solution {
public int countPalindromicSubsequences(String s) {
int MOD = 1000000007;
int n = s.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
if (s.charAt(i) != s.charAt(j)) {
dp[i][j] = ((dp[i+1][j] + dp[i][j-1]) % MOD - dp[i+1][j-1]) % MOD;
} else {
int low = i + 1, high = j - 1;
while (low <= high && s.charAt(low) != s.charAt(i)) low++;
while (low <= high && s.charAt(high) != s.charAt(j)) high--;
if (low > high) {
dp[i][j] = (2 * dp[i+1][j-1] + 2) % MOD;
} else if (low == high) {
dp[i][j] = (2 * dp[i+1][j-1] + 1) % MOD;
} else {
dp[i][j] = ((2 * dp[i+1][j-1]) % MOD - dp[low+1][high-1]) % MOD;
}
}
if (dp[i][j] < 0) dp[i][j] += MOD;
}
}
return dp[0][n-1];
}
}
var countPalindromicSubsequences = function(s) {
const MOD = 1e9 + 7;
const n = s.length;
const dp = Array.from({length: n}, () => Array(n).fill(0));
for (let i = 0; i < n; ++i) dp[i][i] = 1;
for (let len = 2; len <= n; ++len) {
for (let i = 0; i <= n - len; ++i) {
let j = i + len - 1;
if (s[i] !== s[j]) {
dp[i][j] = ((dp[i+1][j] + dp[i][j-1]) % MOD - dp[i+1][j-1]) % MOD;
} else {
let low = i + 1, high = j - 1;
while (low <= high && s[low] !== s[i]) low++;
while (low <= high && s[high] !== s[j]) high--;
if (low > high) {
dp[i][j] = (2 * dp[i+1][j-1] + 2) % MOD;
} else if (low === high) {
dp[i][j] = (2 * dp[i+1][j-1] + 1) % MOD;
} else {
dp[i][j] = ((2 * dp[i+1][j-1]) % MOD - dp[low+1][high-1]) % MOD;
}
}
if (dp[i][j] < 0) dp[i][j] += MOD;
}
}
return dp[0][n-1];
};