题目描述
给你一个字符串 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 仅由小写英文字母组成
解法
方法一：枚举两端字符 + 哈希表
由于字符串中只包含小写字母，因此我们可以直接枚举所有的两端字符。对于每一对两端字符 \(c\)，我们找出它们在字符串中第一次和最后一次出现的位置 \(l\) 和 \(r\)，如果 \(r - l > 1\)，说明找到了满足条件的回文序列，我们将 \([l+1,..r-1]\) 之间的字符去重后统计个数，即为以 \(c\) 为两端字符的回文序列个数，加入答案中。
枚举结束后，即可得到答案。
时间复杂度 \(O(n \times |\Sigma|)\)，其中 \(n\) 为字符串长度，而 \(\Sigma\) 为字符集大小，本题中 \(|\Sigma| = 26\)。空间复杂度 \(O(|\Sigma|)\) 或 \(O(1)\)。
| class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
ans = 0
for c in ascii_lowercase:
l, r = s.find(c), s.rfind(c)
if r - l > 1:
ans += len(set(s[l + 1 : r]))
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public int countPalindromicSubsequence(String s) {
int ans = 0;
for (char c = 'a'; c <= 'z'; ++c) {
int l = s.indexOf(c), r = s.lastIndexOf(c);
int mask = 0;
for (int i = l + 1; i < r; ++i) {
int j = s.charAt(i) - 'a';
if ((mask >> j & 1) == 0) {
mask |= 1 << j;
++ans;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution {
public:
int countPalindromicSubsequence(string s) {
int ans = 0;
for (char c = 'a'; c <= 'z'; ++c) {
int l = s.find_first_of(c), r = s.find_last_of(c);
int mask = 0;
for (int i = l + 1; i < r; ++i) {
int j = s[i] - 'a';
if (mask >> j & 1 ^ 1) {
mask |= 1 << j;
++ans;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | func countPalindromicSubsequence(s string) (ans int) {
for c := 'a'; c <= 'z'; c++ {
l, r := strings.Index(s, string(c)), strings.LastIndex(s, string(c))
mask := 0
for i := l + 1; i < r; i++ {
j := int(s[i] - 'a')
if mask>>j&1 == 0 {
mask |= 1 << j
ans++
}
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function countPalindromicSubsequence(s: string): number {
let ans = 0;
const a = 'a'.charCodeAt(0);
for (let ch = 0; ch < 26; ++ch) {
const c = String.fromCharCode(ch + a);
const l = s.indexOf(c);
const r = s.lastIndexOf(c);
let mask = 0;
for (let i = l + 1; i < r; ++i) {
const j = s.charCodeAt(i) - a;
if (((mask >> j) & 1) ^ 1) {
mask |= 1 << j;
++ans;
}
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | /**
* @param {string} s
* @return {number}
*/
var countPalindromicSubsequence = function (s) {
let ans = 0;
const a = 'a'.charCodeAt(0);
for (let ch = 0; ch < 26; ++ch) {
const c = String.fromCharCode(ch + a);
const l = s.indexOf(c);
const r = s.lastIndexOf(c);
let mask = 0;
for (let i = l + 1; i < r; ++i) {
const j = s.charCodeAt(i) - a;
if (((mask >> j) & 1) ^ 1) {
mask |= 1 << j;
++ans;
}
}
}
return ans;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | public class Solution {
public int CountPalindromicSubsequence(string s) {
int ans = 0;
for (char c = 'a'; c <= 'z'; ++c) {
int l = s.IndexOf(c), r = s.LastIndexOf(c);
int mask = 0;
for (int i = l + 1; i < r; ++i) {
int j = s[i] - 'a';
if ((mask >> j & 1) == 0) {
mask |= 1 << j;
++ans;
}
}
}
return ans;
}
}
|