Medium

题目描述

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

解题思路

解题思路

对于长度为 3 的回文子序列，形式必须是 XYX，其中第一个和第三个字符相同。

核心思路：

  1. 对于每个字符 c，找到它在字符串中的第一次和最后一次出现位置
  2. 在这两个位置之间，统计有多少种不同的字符可以作为中间字符
  3. 对于字符 c，可能的回文数量就是中间不同字符的个数

算法步骤：

  1. 预处理：记录每个字符的第一次和最后一次出现位置
  2. 对于每个出现的字符 c：
    • 如果该字符的第一次和最后一次出现位置不同（至少出现两次）
    • 使用集合统计在这两个位置之间出现的所有不同字符
    • 将集合大小加到结果中

优化点：

  • 只需要遍历 26 个字母
  • 使用位掩码或集合来快速统计中间字符的种类
  • 时间复杂度：O(26 × n) = O(n)

代码实现

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int n = s.length();
        int result = 0;
        
        // 对每个字母，找第一次和最后一次出现的位置
        for (char c = 'a'; c <= 'z'; c++) {
            int first = -1, last = -1;
            
            // 找第一次出现的位置
            for (int i = 0; i < n; i++) {
                if (s[i] == c) {
                    first = i;
                    break;
                }
            }
            
            // 找最后一次出现的位置
            for (int i = n - 1; i >= 0; i--) {
                if (s[i] == c) {
                    last = i;
                    break;
                }
            }
            
            // 如果字符至少出现两次
            if (first != -1 && last != -1 && first < last) {
                unordered_set<char> middle;
                for (int i = first + 1; i < last; i++) {
                    middle.insert(s[i]);
                }
                result += middle.size();
            }
        }
        
        return result;
    }
};

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        result = 0
        
        # 对每个字母，找第一次和最后一次出现的位置
        for c in 'abcdefghijklmnopqrstuvwxyz':
            first = s.find(c)
            last = s.rfind(c)
            
            # 如果字符至少出现两次
            if first != -1 and first < last:
                # 统计中间位置的不同字符
                middle = set(s[first + 1:last])
                result += len(middle)
        
        return result

public class Solution {
    public int CountPalindromicSubsequence(string s) {
        int result = 0;
        
        // 对每个字母，找第一次和最后一次出现的位置
        for (char c = 'a'; c <= 'z'; c++) {
            int first = s.IndexOf(c);
            int last = s.LastIndexOf(c);
            
            // 如果字符至少出现两次
            if (first != -1 && first < last) {
                HashSet<char> middle = new HashSet<char>();
                for (int i = first + 1; i < last; i++) {
                    middle.Add(s[i]);
                }
                result += middle.Count;
            }
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var countPalindromicSubsequence = function(s) {
    let result = 0;
    
    // 对每个字母，找第一次和最后一次出现的位置
    for (let charCode = 97; charCode <= 122; charCode++) {
        const c = String.fromCharCode(charCode);
        const first = s.indexOf(c);
        const last = s.lastIndexOf(c);
        
        // 如果字符至少出现两次
        if (first !== -1 && first < last) {
            const middle = new Set();
            for (let i = first + 1; i < last; i++) {
                middle.add(s[i]);
            }
            result += middle.size;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(26 × n) = O(n)，其中 n 是字符串长度。对每个字母遍历字符串
空间复杂度O(1)，使用的额外空间是常数级别的（最多26个字符的集合）

相关题目