730. Count Different Palindromic Subsequences
Đề Bài
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 <= 1000s[i]is either'a','b','c', or'd'.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n)
💾 Không gian
O(n)
Lời Giải
Python
0730-count-different-palindromic-subsequences.py
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
MOD = 10**9 + 7
@lru_cache(None)
def dp(l, r):
if l > r:
return 0
ans = 0
for c in "abcd":
tl, tr = l, r
while tl <= tr and s[tl] != c:
tl += 1
while tl <= tr and s[tr] != c:
tr -= 1
if tl > tr:
continue
ans = (ans + 1 + (tl != tr) + dp(tl + 1, tr - 1)) % MOD
return ans
return dp(0, len(s) - 1)