LC 730. Count Different Palindromic Subsequences

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

其实这题可以化简成为，对于S[0..n-1]字符串来说：

A: 字符串S[0..n-1]头尾是'a'的回文个数
B,C,D: 字符串S[0..n-1]头尾是'b''c''d'的回文个数
每一类回文因为头尾字符不同肯定是不同的
那么结果就是A+B+C+D

那么如何求解S[0..n-1]头尾是'a'的回文个数呢？

假设最左边'a'是s, 最右边'a'是e的话，
那么就变为了S[s+1, e-1]存在多少个不相同的回文串。

所以统计去重的话，我们可以要求在统计的时候，加上某些限定的条件（比如固定某个前缀等）。一旦加上这些限定条件之后，所得到的结果肯定是不重复的。

在计算到诸如 "a…a"这样的话，是有三类选择的：

只使用a
只使用aa
使用fun(…, a/b/c/d)

def fun(s, e, c):
    if s > e:
        return 0

    key = (s, e, c)
    if key in dp:
        return dp[key]

    # print(s, e, c)
    s = search_right(s, c)
    e = search_left(e, c)
    # print(s, e)
    if s > e:
        ans = 0
    elif s == e:
        ans = 1
    else:
        ans = 2  # 'xx or x'
        for x in range(4):
            ans += fun(s + 1, e - 1, x)
            ans = ans % P
    dp[key] = ans
    return ans

然后另外一个关键就是如何实现 `search_left` 和 `search_right`, 就是找到某个位置之后/之前的最近的某个字符。一种办法使用二分搜索，一个办法则是创建左右索引，这点实现差别对耗时影响还蛮大的，二分搜索大约是10420ms, 左右索引是4052ms.

use_array_index = True

if use_array_index:
    most_right = [n] * 4
    right = [[n] * 4 for _ in range(n)]
    for i in reversed(range(n)):
        x = ord(S[i]) - ord('a')
        most_right[x] = i
        right[i] = most_right.copy()

    most_left = [-1] * 4
    left = [[-1] * 4 for _ in range(n)]
    for i in range(n):
        x = ord(S[i]) - ord('a')
        most_left[x] = i
        left[i] = most_left.copy()

    def search_right(p, c):
        return right[p][c]

    def search_left(p, c):
        return left[p][c]