长度为 3 的不同回文子序列

本题解采用了哈希表和二分查找的结合策略。首先，使用一个哈希表idx来存储每个字符在字符串s中出现的所有索引。接着，遍历哈希表的每个键值对，将当前键作为回文子序列的中心字符。如果中心字符出现次数超过2次，则直接将结果ret加1，因为可以形成如'aaa'这样的回文子序列。然后，对于每一个非中心的字符，使用二分查找检查它是否能够在中心字符的两侧出现，从而形成如'aba'这样的回文子序列。如果可以，结果ret加1。最终，返回结果ret。

时间复杂度: O(n)

空间复杂度: O(n)

from collections import defaultdict
import bisect

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        idx = defaultdict(list)  # 存储每个字符的所有索引
        for i, c in enumerate(s):
            idx[c].append(i)
        ret = 0
        for center in idx:
            if len(idx[center]) > 2:
                ret += 1  # 中心字符出现超过2次，可以形成'aaa'类型的回文子序列
            for appendix in idx.keys():
                if appendix == center:
                    continue
                l = bisect.bisect_left(idx[appendix], idx[center][0])
                r = bisect.bisect_left(idx[appendix], idx[center][-1])
                if l < r:
                    ret += 1  # 存在'aba'类型的回文子序列
        return ret