LeetCode 1930. 长度为 3 的不同回文子序列（计数）

Michael阿明

发布于 2021-09-06 03:18:38

1K00

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

文章目录

- 1. 题目
- 2. 解题

1. 题目

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/unique-length-3-palindromic-subsequences 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

对每个字符左右的字符进行计数
遍历中间字符，同时查找左右两侧的26个字符是否都存在
两侧都存在则将字符串编码成26进制数存入哈希set，最后返回哈希个数

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        vector<int> L(26), R(26);
        L[s[0]-'a']++;
        for(int i = 2; i < s.size(); ++i)
            R[s[i]-'a']++;
        unordered_set<int> set;
        for(int i = 1; i < s.size()-1; ++i)
        {
            for(int j = 0; j < 26; ++j)
            {
                if(L[j] && R[j])
                    set.insert((s[i]-'a')*26+j);
            }
            L[s[i]-'a']++;
            R[s[i+1]-'a']--;
        }
        return set.size();
    }
};