Problem description:

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:

1
2
3
4
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:

1
2
3
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'.

Solution:

The string only contains 'a', 'b', 'c', or 'd'.

dfs+ memo to calculate
find palindrome in substrings and store the count in memo
try to find the occurance of left and right index for “abcd”
if left == right: no same character in the substring, additional is a, which is 1+ dfs(substring)
if left != right: there could be a, aa, a*a, count for this is 2 + dfs(substring)

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
26
27
28
29
class Solution:
class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        memo = {}
        res = set()
        def dfs(start, end):
            if start > end:
                return 0
            if (start, end) in memo:
                return memo[(start, end)]
            
            count = 0
            seg = s[start:end+1]
            for ch in "abcd":
                try:
                    i = seg.index(ch) + start
                    j = seg.rindex(ch) + start
                except:
                    continue
                if i == j:
                    # in this substring, only one ch
                    count += 1
                else:
                    # could make a palindrome with seg[i] and seg[j]
                    # need to find count for seg[i] + dfs(i+1, j-1) + seg[j]
                    count += dfs(i+1, j-1) + 2
            memo[(start, end)] = count % (10 ** 9 + 7)
            return memo[(start, end)]
        return dfs(0, len(s)-1)

time complexity: $O(n^2)$
space complexity: $O(n^2)$
reference:
related problem: