LeetCode 730
The problem seems to be similar to Longest Palindromic Subsequence, but tt’s hard to enumerate all the subsequences since it goes to O(2n) complexity.
Actually, the distinct subsequence is similar to Distinct Subsequences II. We could use the method called Sequence Automata. Check: 序列自动机总结与例题, 序列自动机
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution:
def init_next(self, s: str, a: int) -> List[List[int]]:
n = len(s) - 1
get_next = [[0]*a for _ in range(n+1)]
for i in range(n, 0, -1):
for c in range(a):
get_next[i-1][c] = get_next[i][c]
get_next[i-1][ord(s[i])-ord('a')] = i
return get_next
def countPalindromicSubsequences(self, S: str) -> int:
s1, s2, n, a, mod = ' '+S, ' '+S[::-1], len(S), 4, 10**9+7
next1, next2 = self.init_next(s1, a), self.init_next(s2, a)
def dfs(i, j) -> int:
ans = 0
for c in range(a):
i_n, j_n = next1[i][c], next2[j][c]
if i_n and j_n:
if i_n + j_n > n + 1: continue
if i_n + j_n < n + 1: ans += 1
ans = (ans + dfs(i_n, j_n)) % mod
return ans + 1
return dfs(0, 0) - 1
|