解题思路

1. 一开始还想着dp，可以添加一个新的字符，受到影响的变化规律非常奇怪，然后转变思路
2. 添加一个新的字符能添加多少呢？首先了解回文字符串，就两种，aba和aaa
3. 那么添加新的字符需要回去找原来同样的字符，然后看看中间卡了多少种不同字符
4. 到了这一步我就悟了，真正的核心是前后两个相同字符以及它们之间夹了多少个不同字符
5. 一开始想用前缀和，计数字母的个数，想想空间开销，就离谱，算了
6. 然后回到思路，只需要一前一后，总共也就26个字母，只要遍历每个字母的一前一后，最多时间也是O（n）
7. 于是就有了以下代码，思路理解了，最多遍历26次即可

代码

###cpp

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        //找到一前一后
        map<char, int> first;
        map<char, int> last;
        int size = s.size();
        
        for (int i = 0; i < size; ++i){
            if (first.count(s[i])){
                last[s[i]] = i;
            }else{
                first[s[i]] = i;
            }
        }
        
        int res = 0;
        for (char i = 'a'; i < 'a' + 26; i++){
            if (!first.count(i) || !last.count(i)) continue;
            
            int tL = first[i], tR = last[i];
            vector<int> count(26);
            for (int j = tL + 1; j < tR; ++j){
                count[s[j] - 'a'] = 1;
            }
            
            for (int j = 0; j < 26; ++j){
                if(count[j] == 1) res++;
            }
        }
        
        return res;
    }
};