原文链接: https://leetcode-cn.com/problems/unique-length-3-palindromic-subsequences

英文原文

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

 

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

 

Constraints:

• 3 <= s.length <= 105
• s consists of only lowercase English letters.

中文题目

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

通过代码

高赞题解

解题思路

1. 一开始还想着dp，可以添加一个新的字符，受到影响的变化规律非常奇怪，然后转变思路
2. 添加一个新的字符能添加多少呢？首先了解回文字符串，就两种，aba和aaa
3. 那么添加新的字符需要回去找原来同样的字符，然后看看中间卡了多少种不同字符
4. 到了这一步我就悟了，真正的核心是前后两个相同字符以及它们之间夹了多少个不同字符
5. 一开始想用前缀和，计数字母的个数，想想空间开销，就离谱，算了
6. 然后回到思路，只需要一前一后，总共也就26个字母，只要遍历每个字母的一前一后，最多时间也是O（n）
7. 于是就有了以下代码，思路理解了，最多遍历26次即可

代码

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        //找到一前一后
        map<char, int> first;
        map<char, int> last;
        int size = s.size();
        
        for (int i = 0; i < size; ++i){
            if (first.count(s[i])){
                last[s[i]] = i;
            }else{
                first[s[i]] = i;
            }
        }
        
        int res = 0;
        for (char i = 'a'; i < 'a' + 26; i++){
            if (!first.count(i) || !last.count(i)) continue;
            
            int tL = first[i], tR = last[i];
            vector<int> count(26);
            for (int j = tL + 1; j < tR; ++j){
                count[s[j] - 'a'] = 1;
            }
            
            for (int j = 0; j < 26; ++j){
                if(count[j] == 1) res++;
            }
        }
        
        return res;
    }
};

统计信息

通过次数	提交次数	AC比率
5747	11870	48.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言