b_lc_长度为 3 的不同回文子序列(统计两个相同字符中间有多少个不同字符)

给你一个字符串 s ,返回 s 中 长度为 3 的不同回文子序列 的个数。
即便存在多种方法来构建相同的子序列,但相同的子序列只计数一次。

思路:按照题目来做会比较难搞

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        n = len(s)
        l = collections.defaultdict(int)
        r = collections.defaultdict(int)
        for i in range(n):
            if l.get(s[i], -1) == -1:
                l[s[i]] = i
            else:
                r[s[i]] = i
        
        ans = 0
        for i in range(26):
            c = chr(ord(‘a‘) + i)
            if l.get(c, -1) == -1 or r.get(c, -1) == -1:
                continue
            
            cnt = Counter(s[l[c]+1:r[c]])
            for j in range(26):
                ch = chr(ord(‘a‘) + j)
                if cnt[ch] > 0:
                    ans += 1  
        return ans

b_lc_长度为 3 的不同回文子序列(统计两个相同字符中间有多少个不同字符)

上一篇:Typora源代码模式编写和常用快捷键


下一篇:HTTP请求走私