今日题目

https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/

思路

由于题目要求的是不同子序列的数量，因此最大计数为 $26*26 = 676$。所以我们只需要统计两个相同字符之间有多少个不同的字符即可。

方法

首先计算每个字符首次和最后一次出现的位置，然后在 l 和 r 之间遍历，统计其中有多少个不同的字符。

复杂度

  • 时间复杂度：$O(kN)$，k 为不同字符的数量，此处为 26 个不同字母，N 为字符串长度。

  • 空间复杂度：$O(N)$

代码

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        st = [inf] * 26
        en = [-1] * 26
        a = ord('a')
        for i,ch in enumerate(s):
            nch = ord(ch) - a
            st[nch] = min(st[nch], i)
            en[nch] = max(en[nch], i)

        ans = 0

        for x in range(26):
            if en[x] <= st[x]:
                continue
            # print(en[x], st[x], x)
            vis = set([])
            for i in range(st[x] + 1, en[x]):
                vis.add(s[i])
            ans += len(vis)

        return ans