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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

# 思路

三元组

# 解法

class Solution {
    //三元组, 枚举中间
    //维护每个位置的前后缀, 
    private int count(int n){
        int cnt = 0;
        while(n > 0){
            cnt++;
            n -= -n & n;
        }
        return cnt;
    }

    public int countPalindromicSubsequence(String s) {
        int n = s.length();
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        for(int i = 1; i <= n; i++){
            pre[i] = pre[i - 1] | 1 << (s.charAt(i - 1) - 'a');
        }
        for(int i = n - 2; i >= 0; i--){
            suf[i] |= suf[i + 1] | 1 << (s.charAt(i + 1) - 'a');
        }
        int[] ans = new int[26];
        for(int i = 1; i < n - 1; i++){
            //维护一个26个字母的数字集合, 每次一次性的把前后相同字母添加到 ans
            ans[s.charAt(i) - 'a'] |= (pre[i] & suf[i]); // 1 & 1 = 1
        }
        int res = 0;
        for(int i = 0; i < 26; i++){
            res += count(ans[i]);  //二进制中1的个数, 就是答案的个数
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 总结

分析出几种情况，然后分别对各个情况实现

#Java