给你一个字符串 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
仅由小写英文字母组成
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
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;
}
}
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;
}
};
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
}