目标
给你一个字符串 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 的不同回文子序列个数。
枚举中间元素，同时枚举 a - z 作为左右两侧的字母，判断是否前后都存在。
对字母计数，在枚举过程中记录前面出现字母的次数，结合总次数可以快速判断后面是否存在相同的字母。注意，如果前面出现的字母与枚举的中间字母相同需要将次数减 1。
代码
/**
* @date 2025-11-21 8:44
*/
public class CountPalindromicSubsequence1930 {
public int countPalindromicSubsequence_v1(String s) {
int[] total = new int[26];
char[] chars = s.toCharArray();
for (char c : chars) {
total[c - 'a']++;
}
boolean[][] visited = new boolean[26][26];
int[] prefix = new int[26];
int res = 0;
for (char c : chars) {
prefix[c - 'a']++;
for (int j = 0; j < 26; j++) {
if (!visited[j][c - 'a'] && total[j] > prefix[j] && ((j == c - 'a' && prefix[j] > 1) || j != c - 'a' && prefix[j] > 0)) {
visited[j][c - 'a'] = true;
res++;
}
}
}
return res;
}
}
性能
