长度为 3 的不同回文子序列 图解题解
这道题到底在问什么
- 输入
- s="aabca"
- 输出
- 3（aaa、aba、aca）
- 输入
- s="adc"
- 输出
- 0（凑不出 c?c）
先想最直接的笨办法
记住「枚举两端字符 c → 取它首尾下标 l/r → 中间不同字符种数就是贡献」，下面每帧都在套它。（动画第 3 步）
最优解：一步一步想明白
- 3记住「枚举两端字符 c → 取它首尾下标 l/r → 中间不同字符种数就是贡献」，下面每帧都在套它。
- 4先把回文长相看清:比如两端都是 a，中间夹 b 就是 aba，夹 c 就是 aca。同一个 a?a 只算一次，所以中间字符要去重。下面逐个枚举「两端字符」。
- 5轮到把 a 当两端。先找它第一次出现的位置:下标 0。这是回文左端能放的最靠前的地方。
- 6再找 a 最后一次出现的位置:下标 6。右端放这里最靠后，左右端之间的范围最大，能罩住最多的中间字符。
- 7两端相距 6，大于等于 2，中间至少夹得下一个字符，能凑成 a?a。接下来扫 (0, 6) 之间，数出有几种不同的中间字符。
- 8中间这位是 a，是个新字符，记进集合:{a}。它对应回文 aaa，是一种新的回文。
- 9中间这位是 b，是个新字符，记进集合:{a, b}。它对应回文 aba，是一种新的回文。
- 10中间这位是 c，是个新字符，记进集合:{a, b, c}。它对应回文 aca，是一种新的回文。
- 11中间这位是 c，前面已经见过，去重不重复计——因为 aca 这种回文只能算一次。集合保持 {a, b, c}。
- 12中间这位是 b，前面已经见过，去重不重复计——因为 aba 这种回文只能算一次。集合保持 {a, b, c}。
- 13数完了:中间有 3 种不同字符，所以两端为 a 的回文有 3 个(aaa、aba、aca)。累加进答案，ans = 3。
- 14轮到把 b 当两端。先找它第一次出现的位置:下标 2。这是回文左端能放的最靠前的地方。
- 15再找 b 最后一次出现的位置:下标 5。右端放这里最靠后，左右端之间的范围最大，能罩住最多的中间字符。
- 16两端相距 3，大于等于 2，中间至少夹得下一个字符，能凑成 b?b。接下来扫 (2, 5) 之间，数出有几种不同的中间字符。
- 17中间这位是 c，是个新字符，记进集合:{c}。它对应回文 bcb，是一种新的回文。
- 18中间这位是 c，前面已经见过，去重不重复计——因为 bcb 这种回文只能算一次。集合保持 {c}。
- 19数完了:中间有 1 种不同字符，所以两端为 b 的回文有 1 个(bcb)。累加进答案，ans = 4。
- 20轮到把 c 当两端。先找它第一次出现的位置:下标 3。这是回文左端能放的最靠前的地方。
- 21再找 c 最后一次出现的位置:下标 4。右端放这里最靠后，左右端之间的范围最大，能罩住最多的中间字符。
- 22两端 c 的首尾下标相距只有 1，小于 2，中间夹不下任何字符，凑不成 c?c，直接跳过。ans 不变，还是 4。
- 2326 个字母都当过两端枚举完，累加得到 4 种不同的长度 3 回文:aaa、aba、aca、bcb。回头看，我们没枚举任何子序列，只对每个字符取首尾下标、数中间去重字符，一遍就数清了。
⚠️ 容易写错的地方
✗ 错：把中间字符按出现次数累加
✓ 对：中间字符必须去重，只数「种数」
同一个 c?c 回文只能算一次，中间相同字符重复计就会多算
✗ 错：忘了判 r − l ≥ 2
✓ 对：两端首尾相距至少 2 才夹得下中间字符
字符只出现一次或两次相邻时，中间没有空位，凑不成长度 3 回文
✗ 错：用首尾以外的两个同字符当两端
✓ 对：取最靠前的 first 和最靠后的 last
首尾框定的范围最大，能罩住全部可能的中间字符，不会漏种
完整代码（Python / C++ / Java）
Python
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
ans = 0
for c in set(s):
l = s.find(c)
r = s.rfind(c)
if r - l >= 2:
ans += len(set(s[l + 1:r]))
return ansC++
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int countPalindromicSubsequence(string s) {
vector<int> first(26, -1), last(26, -1);
for (int i = 0; i < (int)s.size(); ++i) {
int c = s[i] - 'a';
if (first[c] == -1) first[c] = i;
last[c] = i;
}
int ans = 0;
for (int c = 0; c < 26; ++c) {
if (last[c] - first[c] >= 2) {
unordered_set<char> mid;
for (int i = first[c] + 1; i < last[c]; ++i) mid.insert(s[i]);
ans += mid.size();
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int countPalindromicSubsequence(String s) {
int[] first = new int[26], last = new int[26];
Arrays.fill(first, -1);
Arrays.fill(last, -1);
for (int i = 0; i < s.length(); i++) {
int c = s.charAt(i) - 'a';
if (first[c] == -1) first[c] = i;
last[c] = i;
}
int ans = 0;
for (int c = 0; c < 26; c++) {
if (last[c] - first[c] >= 2) {
boolean[] seen = new boolean[26];
for (int i = first[c] + 1; i < last[c]; i++) seen[s.charAt(i) - 'a'] = true;
for (boolean b : seen) if (b) ans++;
}
}
return ans;
}
}复杂度
时间
O(26·n)
26 个字母各扫一遍中间区间，n 为串长，常数 26 即字母表大小
空间
O(1)
first/last 各 26 个、中间集合最多 26 个，都是常数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 长度为 3 的不同回文子序列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么两端要取 first 和 last，而不是任意两个相同字符?+
因为 first 最靠前、last 最靠后，它们之间的区间最大，能覆盖所有可能出现在中间的字符；任何用更靠内的两个同字符当端点能凑出的中间字符，first/last 这对都能覆盖到，所以取首尾不漏种。
复杂度里的 26 是怎么来的?+
题目限定小写字母，字母表大小固定为 26。我们对每个字母独立枚举一次、各扫一遍其首尾之间，所以是 26 乘以 n，常数级的字母表大小使它等价于线性。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 长度为 3 的不同回文子序列 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。