长度为3的不同回文子序列-LeetCode

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

🎯 问题描述

描述：
给你一个字符串 s，返回 s 中长度为 3 的不同回文子序列的个数。
即便存在多种方法来构建相同的子序列，只要子序列的内容相同，就视为同一个。
回文串是正着读和反着读一样的字符串。
子序列是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

例如，"aba" 是回文子序列，"abc" 不是。

说明：

• 这是一个枚举首尾字符结合集合去重的问题。

• 核心结构：长度为 3 的回文子序列形式必然是 A B A。

  • 首字符和尾字符必须相同（都是 A）。
  • 中间字符 B 可以是任意字符。

• 策略：

  1. 枚举所有可能的字符 A（从 ‘a’ 到 ‘z’）。
  2. 在字符串 s 中找到 A 第一次出现的位置 i 和 最后一次出现的位置 j。
  3. 任何在 i 和 j 之间出现的字符 B，都可以与首尾的 A 组成一个回文子序列 A B A。
  4. 统计 (i, j) 区间内有多少个不同的字符，就是以 A 为首尾的回文子序列的数量。

• 示例：

• 示例 1：

输入：s = "aabca"
输出：3
解释：
- 字符 'a': 
  - 第一次出现在 i=0，最后一次出现在 j=4。
  - 中间区间 (0, 4) 的子串是 "abc"。
  - 不同的字符有 'a', 'b', 'c'。
  - 可以组成: "aaa", "aba", "aca"。 (3个)
- 字符 'b':
  - 第一次出现在 i=1，最后一次出现在 j=1。
  - 中间区间为空。 (0个)
- 字符 'c':
  - 第一次出现在 i=2，最后一次出现在 j=2。
  - 中间区间为空。 (0个)
- 总数: 3。

💻 解题思路

思路1：枚举首尾字符 + 区间去重

核心逻辑

1. 枚举字符：
   • 遍历 26 个小写字母 alpha。
2. 定位边界：
   • 使用 s.find(alpha) 找到 alpha 在 s 中最左边的下标 i。
   • 使用 s.rfind(alpha) 找到 alpha 在 s 中最右边的下标 j。
   • 如果 i < 0，说明该字符不存在，跳过。
3. 统计中间字符：
   • 我们要找的是形如 alpha + X + alpha 的子序列。
   • 只要字符 X 出现在下标 i 和 j 之间（即 i < k < j），我们就可以选择 s[i], s[k], s[j] 构成回文。
   • 利用 set(s[i+1:j]) 可以快速统计出区间 (i, j) 内有多少种不同的字符。
4. 累加结果：
   • 集合的大小即为当前字符 alpha 能贡献的回文子序列数量。

代码实现

from string import ascii_lowercase

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        ans = 0
        # 1. 枚举所有可能的首尾字符 (a-z)
        for alpha in ascii_lowercase:
            # 2. 找到该字符在 s 中第一次出现的位置
            i = s.find(alpha)
            
            # 如果字符不存在，跳过
            if i < 0:
                continue
                
            # 3. 找到该字符在 s 中最后一次出现的位置
            j = s.rfind(alpha)
            
            # 4. 统计 (i, j) 区间内不同字符的个数
            # s[i+1:j] 获取中间部分的子串
            # set() 去重后，长度即为不同中间字符的数量
            ans += len(set(s[i + 1: j]))
            
        return ans

📊 性能分析

• 时间复杂度：$O(26 \times N) \approx O(N)$
  • 其中 $N$ 是字符串 s 的长度。
  • 外层循环固定执行 26 次（小写字母个数）。
  • find 和 rfind 操作各需要 $O(N)$。
  • set(s[i+1:j]) 在最坏情况下（首尾分别是第一个和最后一个字符）需要遍历整个字符串，耗时 $O(N)$。
  • 总时间复杂度为 $O(26 \times N)$，即线性时间。
• 空间复杂度：$O(1)$ 或 $O(N)$
  • set 在最坏情况下存储所有字符，但由于字符集只有 26 个小写字母，集合的大小上限是 26。
  • 因此，严格来说空间复杂度是 $O(1)$（常数级）。
  • 切片 s[i+1:j] 会产生新的字符串副本，这在 Python 中是 $O(N)$ 的空间，但在算法分析中通常关注辅助空间，这里主要是集合的大小。

思考

1. 为什么只需要找第一次和最后一次出现的位置？

   • 我们要最大化中间可选字符的范围。
   • 假设字符 A 出现在下标 $p_1, p_2, ..., p_k$。
   • 如果我们选 $p_1$ 和 $p_k$ 作为首尾，中间区间是 $(p_1, p_k)$。
   • 如果我们选任意其他对 $(p_x, p_y)$，区间 $(p_x, p_y)$ 必然是 $(p_1, p_k)$ 的子区间。
   • 因此，选择最外侧的一对 A，能包含最多的中间字符，从而得到所有可能的回文子序列。

2. 集合去重的作用：

   • 题目要求“不同”的回文子序列。
   • 例如 s = "abaca"，首尾是 a。中间有 b, a, c。
   • 虽然 a 出现了两次，但 aaa 这个子序列只算一次。
   • set 完美解决了这个问题。

3. Python 内置函数的便利性：

   • s.find() 和 s.rfind() 非常高效且易读。
   • 如果不使用内置函数，也可以预处理每个字符出现的所有下标列表，然后取首尾，但代码会更长。

4. 边界情况：

   • 字符只出现一次：i == j，切片 s[i+1:j] 为空，贡献为 0。
   • 字符相邻：j == i + 1，切片为空，贡献为 0。
   • 字符串长度小于 3：无法构成回文，循环中 i 和 j 无法满足条件或中间为空，返回 0。