题目

给你一个字符串 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" ("**bbcb**aba" 的子序列)
"bcb" ("**bbcb**aba" 的子序列)
"bab" ("**bbcbab**a" 的子序列)
"aba" ("bbcb**aba**" 的子序列)

提示：

3 <= s.length <= 10^5
s 仅由小写英文字母组成

解题思路

题目要求寻找长度为 3 的回文子序列。

任何长度为 3 的回文形式必然是 "XYX"。

即：第 1 个字符和第 3 个字符必须相同，中间的第 2 个字符可以是任意字符。

要找到所有唯一的 "XYX" 形式，我们可以采取以下策略：

枚举外层字符（X）：由于字符集很小（仅小写字母 'a'-'z'，共 26 个），我们可以遍历这 26 个字母，把每一个都尝试作为回文的“外壳”字符 $X$。
确定边界（贪心思想）：对于每一个字符 $X$（例如 'a'），为了让中间能容纳尽可能多的不同字符 $Y$，我们需要让两个 $X$ 之间的距离最大化。
- 找到 $X$ 在字符串 $s$ 中第一次出现的位置（记为 first）。
- 找到 $X$ 在字符串 $s$ 中最后一次出现的位置（记为 last）。
统计中间字符（Y）：如果 first 和 last 存在，且 last > first + 1（说明中间至少有一个字符），那么在索引区间 (first, last) 之间的所有不重复字符，都可以充当 $Y$。
- 此时，以 $X$ 为外壳的回文子序列数量，就等于该区间内不重复字符的个数。
累加结果：将每一个字母作为外壳时计算出的个数累加，即为最终答案。

算法步骤详解

预处理索引：遍历字符串，记录每一个字符 'a'-'z' 第一次出现的下标 first[26] 和最后一次出现的下标 last[26]。
- 初始化 first 数组全为 -1。
- 遍历时，如果某字符对应 first 为 -1，则记录当前下标；同时不断更新 last 为当前下标。
遍历字母表：从 'a' 到 'z' 进行循环：
- 获取当前字母的起始位置 start 和结束位置 end。
- 如果 start == -1 或 start == end（只有一个或不存在），跳过。
- 截取字符串 $s$ 在下标 start + 1 到 end - 1 之间的部分。
- 统计这部分子串中唯一字符的种类数量（可以使用哈希集合 Set 去重）。
- 将集合的大小加到总结果中。
返回总数。

复杂度分析

时间复杂度： $O(N)$
- 第一次遍历字符串记录首尾位置：$O(N)$。
- 之后循环 26 次（常数级）。
- 在每次循环中，最坏情况下需要再次遍历整个字符串（例如全也是 'a' 的情况），但因为外层只有 26 次，所以整体大概是 $26 \times N$，即 $O(N)$。
空间复杂度： $O(1)$
- 我们需要保存首尾索引数组（大小 26）和中间字符的集合（最大大小 26），这相对于输入规模 $N$ 来说是常数空间。

具体代码

func countPalindromicSubsequence(s string) int {
    // 1. 使用数组代替 Map，索引 0-25 对应 'a'-'z'
    // 初始化为 -1 表示未出现
    first := make([]int, 26)
    last := make([]int, 26)
    for i := 0; i < 26; i++ {
        first[i] = -1
        last[i] = -1
    }

    // 2. 一次遍历记录首尾位置
    // 既然是 ASCII，直接按字节遍历不仅更快，而且类型统一
    for i := 0; i < len(s); i++ {
        idx := s[i] - 'a' // 将 byte 映射到 0-25
        if first[idx] == -1 {
            first[idx] = i
        }
        last[idx] = i // 不断更新最后出现的位置
    }

    ans := 0
    // 3. 遍历 26 个字母
    for k := 0; k < 26; k++ {
        start, end := first[k], last[k]
        
        // 如果该字母出现过，且首尾之间有间隔
        if start != -1 && end > start + 1 {
            // 使用 boolean 数组标记中间出现过的字符
            // 这里只在栈上分配，速度极快，且 Go 编译器会优化这个小数组
            seen := [26]bool{}
            count := 0
            
            // 遍历中间段
            for i := start + 1; i < end; i++ {
                charIdx := s[i] - 'a'
                if !seen[charIdx] {
                    seen[charIdx] = true
                    count++
                    // 剪枝：如果中间已经集齐 26 个字母，就不用继续找了
                    if count == 26 {
                        break
                    }
                }
            }
            ans += count
        }
    }

    return ans
}

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

beautifulremi

题目

解题思路

算法步骤详解

复杂度分析

具体代码