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 10^9 + 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 10^9 + 7.
Constraints:
1 <= s.length <= 1000
s[i]
is either 'a'
, 'b'
, 'c'
, or 'd'
.A brute force approach would involve generating all possible subsequences of the input string s
, checking if each subsequence is a palindrome, and then counting the distinct palindromic subsequences. This approach is highly inefficient due to the exponential number of subsequences a string can have.
A more efficient approach involves using dynamic programming. We can define dp[i][j]
as the number of distinct palindromic subsequences in the substring s[i...j]
. The base cases are when i > j
, dp[i][j] = 0
, and when i == j
, dp[i][j] = 1
(a single character is a palindrome).
The recurrence relation is as follows:
s[i] != s[j]
, then dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
. We subtract dp[i+1][j-1]
to avoid double-counting the palindromic subsequences in s[i+1...j-1]
.s[i] == s[j]
, we need to consider the characters between i
and j
:
i
and j
, then dp[i][j] = 2 * dp[i+1][j-1] + 2
. The 2 * dp[i+1][j-1]
accounts for all palindromic subsequences in s[i+1...j-1]
with the outer characters s[i]
and s[j]
added, and the + 2
accounts for the single character s[i]
and the two-character palindrome s[i]s[j]
.i
and j
at index l
, then dp[i][j] = 2 * dp[i+1][j-1] + 1
. The + 1
accounts for the single character s[i]
which is the same as s[l]
.i
and j
, let the leftmost be at index l
and the rightmost be at index r
, then dp[i][j] = 2 * dp[i+1][j-1] - dp[l+1][r-1]
. We subtract dp[l+1][r-1]
because the palindromic subsequences in s[l+1...r-1]
were double-counted.We need to apply modulo 10^9 + 7
during each calculation to prevent integer overflow.
def count_palindromic_subsequences(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
mod = 10**9 + 7
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]:
l = i + 1
r = j - 1
while l <= r and s[l] != s[i]:
l += 1
while l <= r and s[r] != s[i]:
r -= 1
if l > r:
dp[i][j] = (2 * dp[i + 1][j - 1] + 2) % mod
elif l == r:
dp[i][j] = (2 * dp[i + 1][j - 1] + 1) % mod
else:
dp[i][j] = (2 * dp[i + 1][j - 1] - dp[l + 1][r - 1]) % mod
if dp[i][j] < 0:
dp[i][j] += mod
else:
dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]) % mod
if dp[i][j] < 0:
dp[i][j] += mod
return dp[0][n - 1]