Problem statement

https://leetcode.com/problems/count-different-palindromic-subsequences/

Solution

The idea is to define dp[i, j] be the answer for substing S[i:j+1] (we also count empty substing, so we will subtract 1 in the end). Then let us find the leftest and the rightest a in this substing: it will be number of unique substrings with ending elements equal to a. In the same way we evaluate number of substrings with ending elements b, c, d. Also we need to check one more border case: substrings with length 1.

Complexity

Time complexity is O(n^2d), where d = 4 here is size of alphabet, space complexity is O(n^2).

Code

class Solution:
    def countPalindromicSubsequences(self, S):
        def letter_get(s, letter, dir):
            res, cur = [-1]*len(s), -1
            for i in range(len(s))[::dir]:
                if s[i] == letter: cur = i
                res[i] = cur
            return res

        corrs_dir = defaultdict(list)
        corrs_inv = defaultdict(list)
        for letter in "abcd":
            corrs_dir[letter] = letter_get(S, letter, 1)
            corrs_inv[letter] = letter_get(S, letter, -1)

        n, MOD = len(S), 10**9 + 7
        @lru_cache(None)
        def dp(i, j):
            if i > j: return 1
            ans = 1
            for letter in "abcd":
                i0 = corrs_inv[letter][i]
                j0 = corrs_dir[letter][j]
                if i <= i0 <= j: ans += 1               #single letter
                if -1 < i0 < j0: ans += dp(i0+1, j0-1)  #...X_X... case
            return ans % MOD

        return dp(0, n-1) - 1