Untitled

 avatar
unknown
plain_text
a month ago
1.1 kB
2
Indexable
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        unordered_map<char, vector<int>> mapItems;
        int ss= s.size();
        for(int i=0;i<ss;i++){
            mapItems[s[i]].push_back(i);
        }
        int res=0;

        for(auto cur: mapItems){
            char stChar= cur.first;
            if(cur.second.size()>=2){
                int totalSize= cur.second.size();
                int firstCharIndex= cur.second[0];
                int lastCharINdex= cur.second[totalSize-1];
                for(auto mid: mapItems){
                    int midTotalSize= mid.second.size();
                    auto itr= 
                        upper_bound(mid.second.begin(), mid.second.end(), firstCharIndex);
                    
                    if(itr!=mid.second.end()){
                        int index= itr - mid.second.begin();
                        if(mid.second[index]<lastCharINdex) res++;
                    }


                }
            }
        }

        return res;
    }
};
Leave a Comment