class Solution {
public:
int countPalindromicSubsequence(string s) {
}
};
1930. 长度为 3 的不同回文子序列
给你一个字符串 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 <= 105s 仅由小写英文字母组成原站题解
golang 解法, 执行用时: 36 ms, 内存消耗: 6 MB, 提交时间: 2022-12-14 11:49:54
/**
* 枚举回文子序列的中间字符，并枚举其左右字符（从 a 到 z），若该字符在中间字符左右侧均存在，则找到一个回文子序列。
* 我们可以在枚举中间字符的同时，计算字符串的前缀和与后缀和，这样就能判断某个字符在中间字符左右侧均存在。
* 由于题目要求相同的子序列只计数一次，我们可以用一个 26⋅26 的布尔数组记录每个回文子序列是否存在。
* 代码实现时可以将布尔数组的第二维用位运算压掉。
**/
func countPalindromicSubsequence(s string) (ans int) {
var pre, suf, has [26]int
for _, ch := range s[1:] {
suf[ch-'a']++
}
for i := 1; i < len(s)-1; i++ { // 枚举回文子序列的中间字符
pre[s[i-1]-'a']++
suf[s[i]-'a']--
for j := 0; j < 26; j++ { // 枚举中间字符的左右字符
if pre[j] > 0 && suf[j] > 0 { // 找到了一个回文子序列
has[s[i]-'a'] |= 1 << j
}
}
}
for _, mask := range has {
ans += bits.OnesCount(uint(mask)) // 累加二进制中 1 的个数即为答案
}
return
}
cpp 解法, 执行用时: 280 ms, 内存消耗: 12.6 MB, 提交时间: 2022-12-14 11:48:46
class Solution {
public:
int countPalindromicSubsequence(string s) {
int n = s.size();
int res = 0;
// 枚举两侧字符
for (char ch = 'a'; ch <= 'z'; ++ch){
int l = 0, r = n - 1;
// 寻找该字符第一次出现的下标
while (l < n && s[l] != ch){
++l;
}
// 寻找该字符最后一次出现的下标
while (r >= 0 && s[r] != ch){
--r;
}
if (r - l < 2){
// 该字符未出现，或两下标中间的子串不存在
continue;
}
// 利用哈希集合统计 s[l+1..r-1] 子串的字符总数，并更新答案
unordered_set<char> charset;
for (int k = l + 1; k < r; ++k){
charset.insert(s[k]);
}
res += charset.size();
}
return res;
}
};
cpp 解法, 执行用时: 40 ms, 内存消耗: 19.5 MB, 提交时间: 2022-12-14 11:48:30
class Solution {
public:
int countPalindromicSubsequence(string s) {
int n = s.size();
int res = 0;
// 前缀/后缀字符状态数组
vector<int> pre(n), suf(n);
for (int i = 0; i < n; ++i) {
// 前缀 s[0..i-1] 包含的字符种类
pre[i] = (i ? pre[i-1] : 0) | (1 << (s[i] - 'a'));
}
for (int i = n - 1; i >= 0; --i) {
// 后缀 s[i+1..n-1] 包含的字符种类
suf[i] = (i != n - 1 ? suf[i+1] : 0) | (1 << (s[i] - 'a'));
}
// 每种中间字符的回文子序列状态数组
vector<int> ans(26);
for (int i = 1; i < n - 1; ++i) {
ans[s[i]-'a'] |= (pre[i-1] & suf[i+1]);
}
// 更新答案
for (int i = 0; i < 26; ++i) {
res += __builtin_popcount(ans[i]);
}
return res;
}
};
python3 解法, 执行用时: 576 ms, 内存消耗: 23.1 MB, 提交时间: 2022-12-14 11:48:19
# 枚举中间字符
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
n = len(s)
res = 0
# 前缀/后缀字符状态数组
pre = [0] * n
suf = [0] * n
for i in range(n):
# 前缀 s[0..i-1] 包含的字符种类
pre[i] = (pre[i-1] if i else 0) | (1 << (ord(s[i]) - ord('a')))
for i in range(n - 1, -1, -1):
# 后缀 s[i+1..n-1] 包含的字符种类
suf[i] = (suf[i+1] if i != n - 1 else 0) | (1 << (ord(s[i]) - ord('a')))
# 每种中间字符的回文子序列状态数组
ans = [0] * 26
for i in range(1, n - 1):
ans[ord(s[i])-ord('a')] |= pre[i-1] & suf[i+1]
# 更新答案
for i in range(26):
res += bin(ans[i]).count("1")
return res
python3 解法, 执行用时: 2576 ms, 内存消耗: 15.5 MB, 提交时间: 2022-12-14 11:47:56
# 枚举两侧字符
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
n = len(s)
res = 0
# 枚举两侧字符
for i in range(26):
l, r = 0, n - 1
# 寻找该字符第一次出现的下标
while l < n and ord(s[l]) - ord('a') != i:
l += 1
# 寻找该字符最后一次出现的下标
while r >= 0 and ord(s[r]) - ord('a') != i:
r -= 1
if r - l < 2:
# 该字符未出现，或两下标中间的子串不存在
continue
# 利用哈希集合统计 s[l+1..r-1] 子串的字符总数，并更新答案
charset = set()
for k in range(l + 1, r):
charset.add(s[k])
res += len(charset)
return res