<p>Given a string <code>s</code>, return <em>the number of <strong>unique palindromes of length three</strong> that are a <strong>subsequence</strong> of </em><code>s</code>.</p>

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

<p>A <strong>palindrome</strong> is a string that reads the same forwards and backwards.</p>

<p>A <strong>subsequence</strong> 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.</p>

<ul>
	<li>For example, <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;<u>a</u>b<u>c</u>d<u>e</u>&quot;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aabca&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The 3 palindromic subsequences of length 3 are:
- &quot;aba&quot; (subsequence of &quot;<u>a</u>a<u>b</u>c<u>a</u>&quot;)
- &quot;aaa&quot; (subsequence of &quot;<u>aa</u>bc<u>a</u>&quot;)
- &quot;aca&quot; (subsequence of &quot;<u>a</u>ab<u>ca</u>&quot;)
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;adc&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no palindromic subsequences of length 3 in &quot;adc&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bbcbaba&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> The 4 palindromic subsequences of length 3 are:
- &quot;bbb&quot; (subsequence of &quot;<u>bb</u>c<u>b</u>aba&quot;)
- &quot;bcb&quot; (subsequence of &quot;<u>b</u>b<u>cb</u>aba&quot;)
- &quot;bab&quot; (subsequence of &quot;<u>b</u>bcb<u>ab</u>a&quot;)
- &quot;aba&quot; (subsequence of &quot;bbcb<u>aba</u>&quot;)
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

// class Solution {
// public:
//     int countPalindromicSubsequence(string s) {

//         vector<int> vec = {};
//         int total = 0;

//         for(int i = 0; i<s.size(); i++) {
//             int start = 0;
//             int end = 0;
            
//             if(std::find(vec.begin(), vec.end(), s[i]) != vec.end()) {
//                 continue;
//             } else {
//                 start = i;
//                 for(int j = i + 1; j<s.size(); j++) {
//                     if(s[i] == s[j] && j - i > 1) {
//                         end = j;
//                         map<char, int> m;
//                         int two = 0;
//                         int len = s.size();

//                         for(int z = start; z <= end; z++) {
//                             m[s[z]]++;
//                         }

//                         for(auto it : m) {
//                             if(it.second == 2) {
//                                 two+=1;
//                                 len -= 2;
//                             }

//                             if(it.second > 2) {
//                                 two+=1;
//                                 len -= 2;
//                                 len -= it.second - 2;
//                                 len++;

//                             }
//                         }
//                         total += two * len;
//                         vec.push_back(s[i]);
//                     }
//                 }
//             }
//         }
//         return total;
//     }
// };

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

class Solution {
public:
    int countPalindromicSubsequence(std::string s) {

        std::vector<char> processed;  // Store processed characters to avoid duplicate work
        int total = 0;

        for (int i = 0; i < s.size(); i++) {
            // Skip if character is already processed
            if (std::find(processed.begin(), processed.end(), s[i]) != processed.end()) {
                continue;
            }

            processed.push_back(s[i]);  // Mark this character as processed

            // Find the last occurrence of s[i]
            int start = i;
            int end = s.rfind(s[i]);

            // If the character doesn't appear at least twice, skip it
            if (end == -1 || end <= start + 1) {
                continue;
            }

            // Use a set to track unique characters between start and end
            std::set<char> unique_chars;
            for (int j = start + 1; j < end; j++) {
                unique_chars.insert(s[j]);
            }

            // Add the number of unique characters to the total count
            total += unique_chars.size();
        }

        return total;
    }
};
15119