给你一个字符串 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