README.md

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

English Version

题目描述

给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。

即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。

回文 是正着读和反着读一样的字符串。

子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

• 例如，"ace" 是 "abcde" 的一个子序列。

 

示例 1：

输入：s = "aabca"
输出：3
解释：长度为 3 的 3 个回文子序列分别是：
- "aba" ("aabca" 的子序列)
- "aaa" ("aabca" 的子序列)
- "aca" ("aabca" 的子序列)

示例 2：

输入：s = "adc"
输出：0
解释："adc" 不存在长度为 3 的回文子序列。

示例 3：

输入：s = "bbcbaba"
输出：4
解释：长度为 3 的 4 个回文子序列分别是：
- "bbb" ("bbcbaba" 的子序列)
- "bcb" ("bbcbaba" 的子序列)
- "bab" ("bbcbaba" 的子序列)
- "aba" ("bbcbaba" 的子序列)

 

提示：

• 3 <= s.length <= 105
• s 仅由小写英文字母组成

解法

Python3

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = 0
        for i in range(26):
            c = chr(ord('a') + i)
            if c in s:
                l, r = s.index(c), s.rindex(c)
                chars = {s[j] for j in range(l + 1, r)}
                res += len(chars)
        return res

Java

class Solution {
    public int countPalindromicSubsequence(String s) {
        int res = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.indexOf(c), r = s.lastIndexOf(c);
            Set<Character> chars = new HashSet<>();
            for (int i = l + 1; i < r; ++i) {
                chars.add(s.charAt(i));
            }
            res += chars.size();
        }
        return res;
    }
}

C++

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int res = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.find_first_of(c), r = s.find_last_of(c);
            unordered_set<char> chars;
            for (int i = l + 1; i < r; ++i) {
                chars.insert(s[i]);
            }
            res += chars.size();
        }
        return res;
    }
};

Go

func countPalindromicSubsequence(s string) int {
	res := 0
	for c := 'a'; c <= 'z'; c++ {
		l, r := strings.Index(s, string(c)), strings.LastIndex(s, string(c))
		chars := make(map[byte]bool)
		for i := l + 1; i < r; i++ {
			chars[s[i]] = true
		}
		res += len(chars)
	}
	return res
}

...