Count Different Palindromic Subsequences LeetCode solution in Python

1
class Solution:
2
    def countPalindromicSubsequences(self, s: str) -> int:
3

4
        N = len(s)
5
        mod = 10**9 + 7
6
        memo = {}
7

8
        def backTrack(start, end):
9

10
            if start >= N or end < 0:
11
                return 0
12

13
            key = (start, end)
14

15
            if key in memo:
16
                return memo[key]
17

18
            strn = s[start : end + 1]
19

20
            memo[key] = 0
21

22
            for char in "abcd":
23
                if not char in strn:
24
                    continue
25
                i = start + strn.index(char)
26
                j = start + strn.rindex(char)
27
                memo[key] += backTrack(i + 1, j - 1) + 2 if i != j else 1
28

29
            memo[key] %= mod
30

31
            return memo[key]
32

33
        return backTrack(0, N - 1)