Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.


	For example, "ace" is a subsequence of "abcde".


&nbsp;
Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")


Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".


Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")


&nbsp;
Constraints:


	3 &lt;= s.length &lt;= 105
	s consists of only lowercase English letters.


class Solution(object):
    def countPalindromicSubsequence(self, s):
        d=defaultdict(list)
        for i,c in enumerate(s):
            d[c].append(i)
        ans=0
        for el in d:
            if len(d[el])<2:
                continue
            a=d[el][0]
            b=d[el][-1]
            ans+=len(set(s[a+1:b]))
        return(ans)
class Solution {
    public int countPalindromicSubsequence(String s) {
        
        int n = s.length();
        
        char[] chArr = s.toCharArray();
        
        int[] firstOcc = new int[26];
        int[] lastOcc = new int[26];
        
        Arrays.fill(firstOcc, -1);
        Arrays.fill(lastOcc, -1);
        
        for(int i = 0; i < n; i++){
            
            char ch = chArr[i];
            
            if(firstOcc[ch - 'a'] == -1){
                firstOcc[ch - 'a'] = i;
            }
            
            lastOcc[ch - 'a'] = i;
        }
        
        int ans = 0, count = 0;
        
        boolean[] visited;
        
		// check for each character ( start or end of palindrome )
        for(int i = 0; i < 26; i++){
            
            int si = firstOcc[i]; // si - starting index
            int ei = lastOcc[i]; // ei - ending index
            
            visited = new boolean[26];
            
            count = 0;
            
			// check for unique charcters ( middle of palindrome )
            for(int j = si + 1; j < ei; j++){
                
                if(!visited[chArr[j] - 'a']){
                    visited[chArr[j] - 'a'] = true;
                    count++;
                }
            }
            
            ans += count;
        }
        
        return ans;
    }
}
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        
        vector<pair<int, int> > v(26, {-1, -1} ); //to store first occurance  and last occurance of every alphabet.
        
        int n = s.length(); //size of the string
        
        for (int i = 0 ; i< n ;i++ ){
            if (v[s[i] - 'a'].first == -1 ) v[s[i] - 'a'].first = i; // storing when alphabet appered first time.
            else v[s[i] - 'a'].second = i; // else whenever it appears again. So that the last occurrence will be stored at last.
        }
        
        int ans = 0 ;
        for (int i = 0 ; i <26 ;i++ ){ //traversing over all alphabets.

            if (v[i].second != -1 ){ //only if alphabet occured second time.
                
                unordered_set<char> st; //using set to keep only unique elements between the range.
                
                for (int x = v[i].first + 1 ; x < v[i].second ; x++ ) st.insert(s[x]); // set keeps only unique elemets.
                    
                ans += ((int)st.size()); // adding number of unique elements to the answer.
            }
        }
        return ans;
        
    }
};
var countPalindromicSubsequence = function(s) {
    const charToIndices = {};
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (charToIndices[char]) {
            charToIndices[char].push(i);
        } else {
            charToIndices[char] = [i];
        }
    }

    let count = 0;
    for (const currChar in charToIndices) {
        if (charToIndices[currChar].length < 2) continue;
        const currCharIndices = charToIndices[currChar];
        const firstIndex = currCharIndices[0];
        const lastIndex = currCharIndices[currCharIndices.length - 1];

        for (const char in charToIndices) {
            const indices = charToIndices[char];
            let lo = 0;
            let hi = indices.length;
            while (lo < hi) {
                const mid = (lo + hi) >> 1;
                if (indices[mid] <= firstIndex) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            if (indices[lo] && indices[lo] < lastIndex) {
                count++;
            }
        }
    }
    return count;
};
Unique Length-3 Palindromic Subsequences